6.1.3. Negative Cycles

The final characterization of a minimum-cost flow considers the cost of cycles in the residual network \(G^f\), where the cost of a cycle is the sum of the costs of its edges.

Lemma 6.3: A flow \(f\) is a minimum-cost flow if and only if the residual network \(G^f\) has no negative cycle (cycle of negative cost).

Intuitively, at least the "only if" direction is obvious because, if there exists a negative-cost cycle in \(G^f\), then we can reduce \(f\)'s cost by sending some positive amount of flow \(\delta\) along such a cycle. We can choose \(\delta\) small enough that the resulting modified flow \(f'\) continues to satisfy the capacity constraints. \(f'\) also satisfies the flow conservation constraints because \(f\) does and sending flow along any cycle does not change the net outflow of any vertex.

Proof: First assume that \(f\) is a minimum-cost flow. By Lemma 6.2, there exists a potential function \(\pi\) such that \(c^\pi_{x,y} \ge 0\) for every edge \((x, y) \in G^f\). Next observe that every cycle \(C\) in \(G^f\) satisfies

\[\sum_{(x,y) \in C} c^\pi_{x,y} = \sum_{(x,y) \in C} c^f_{x,y} - \sum_{x \in C} \pi_x + \sum_{y \in C} \pi_y = \sum_{(x, y) \in C} c^f_{x,y}.\]

Since every edge in \(G^f\) satisfies \(c^\pi_{x,y} \ge 0\), the first sum is non-negative, that is, \(G^f\) contains no negative cycle.

Now assume that \(G^f\) contains no negative cycle. Then we transform \(G^f\) into a graph \(H^f\) by choosing a distinguished vertex \(s \in V\) and adding an edge from \(s\) to every vertex \(x \in V \setminus \{s\}\). Choose the cost of each such edge \((s, x)\) to be equal to \(\sum_{e \in G^f} \bigl|c^f_e\bigr|\). Then every vertex in \(H^f\) is reachable from \(s\) and \(H^f\) contains no negative cycle. Indeed, any cycle that contains only edges in \(G^f\) has a non-negative cost. Any cycle that includes at least one edge \((s, x)\) has cost at least

\[\sum_{e \in G^f} \Bigl|c^f_e\Bigr| + \sum_{\substack{e \in G^f\\c^f_e < 0}} c^f_e \ge 0.\]

Since every vertex is reachable from \(s\) in \(H^f\) and \(H^f\) has no negative cycles, every vertex \(x \in V\) has a well defined distance \(d_x\) from \(s\) in \(H_f\) with respect to the edge costs as edge lengths. We define a potential function \(\pi\) as

\[\pi_x = -d_x \quad \forall x \in V.\]

Then every edge \((x, y)\) in \(H^f\) satisfies

\[d_y \le d_x + c^f_{x,y},\]

that is,

\[c^\pi_{x,y} = c_{x,y}^f - \pi_x + \pi_y \ge 0.\]

Since every edge of \(G^f\) is also an edge of \(H^f\), this shows that \(f\) and \(\pi\) satisfy the condition of Lemma 6.2, so \(f\) is a minimum-cost flow in \(G\). ▨