6.3.2. Limiting Edge Capacities

Some of the minimum-cost flow algorithms discussed here require that all edge costs are non-negative. The transformation that ensures this, discussed in Section 6.3.4, assumes in turn that all edges have finite capacities. Here, we discuss how to equip each uncapacitated edge with a finite capacity without changing the minimum-cost flow in the network.

Note that a minimum-cost flow is well defined only if there is no negative-cost cycle of unbounded capacity in \(G\): Otherwise, we could send an arbitrarily large amount of flow along such a cycle to decrease the cost of the flow as much as we want. Under this assumption, the following lemma shows that we can turn all uncapacitated edges into capacitated ones without changing the cost of a minimum-cost flow.

Lemma 6.10: Let \(H\) be the network obtained from \(G\) by setting the capacity of every uncapacitated edge to

\[\sum_{\substack{x \in V\\b_x > 0}} b_x + \sum_{e \in E_b} u_e.\]

If \(G\) has no negative-cost cycle of unbounded capacity, then every minimum-cost flow in \(H\) is a minimum-cost flow in \(G\).

Proof: Clearly, every flow in \(H\) is also a flow in \(G\). In particular, every minimum-cost flow in \(H\) is a flow in \(G\). Next we show that there exists a minimum-cost flow in \(G\) that is a flow in \(H\). Thus, every minimum-cost flow in \(H\) is a minimum-cost flow of \(G\).

So consider a minimum-cost flow \(f\) in \(G\) and decompose it into path or cycle flows \(f^{(1)}, \ldots, f^{(t)}\) as in Lemma 6.5. Observe that the cost of every cycle flow \(f^{(i)}\) is non-positive because otherwise the flow \(f - f^{(i)}\) would be a flow in \(G\) of lower cost, contradicting the optimality of \(f\). We can also assume that there is no cycle flow \(f^{(i)}\) of cost zero, that is, that every cycle flow in the decomposition has strictly negative cost. Indeed, we can remove all cycle flows of cost zero from the decomposition and redefine \(f\) as the sum of the remaining path or cycle flows in the decomposition without changing the cost of \(f\).

Now observe that every path flow \(f^{(i)}\) carries some amount of flow \(a\) from a supply node \(x\) to a demand node, and path flows are in fact the only flows in the decomposition that move any flow from supply nodes to demand nodes. Thus, the total flow carried by all path flows is

\[\sum_{\substack{x \in V\\b_x > 0}} b_x.\]

Next consider a capacitated edge \(e\). The total flow carried by all cycle flows that use this edge is at most \(u_e\). Since every cycle flow \(f^{(i)}\) has negative cost and there are no uncapacitated cycles of negative cost in \(G\), every cycle flow \(f^{(i)}\) must include at least one capacitated edge. Thus, the total flow carried by all cycle flows in the decomposition is at most

\[\sum_{e \in E_b} u_e.\]

Finally, observe that an uncapacitated edge is used at most by all path flows and by all cycle flows in the composition. Thus, \(f\) sends at most

\[\sum_{\substack{x \in V\\b_x > 0}} b_x + \sum_{e \in E_b} u_e\]

units of flow along every uncapacitated edge \(e'\) of \(G\). Since this is the capacity of \(e'\) in \(H\), \(f\) thus satisfies the capacity constraints of \(H\) and is a flow in \(H\). ▨