6.4. Negative Cycle Cancelling

The negative cycle optimality criterion of a minimum-cost flow established by Lemma 6.3 leads to our first, simple algorithm for computing a minimum-cost flow in a network.

This algorithm assumes that all edge capacities and edge costs are integers.

This integrality assumption is one we cannot eliminate using a simple transformation of the network. Thus, this algorithm really only works for integral edge capacities and edge costs.

The algorithm proceeds in two phases: In the first phase, it finds a feasible flow or decides that no such flow exists. In the case of maximum \(st\)-flows, the flow \(f\) defined as \(f_e = 0\) for all \(e \in G\) is a feasible flow, so there always exists a feasible \(st\)-flow. When looking for a minimum-cost flow, every vertex has a specific supply balance and it is not guaranteed that the edge capacities of the network allow us to send all the supply provided by supply nodes to appropriate demand nodes. Thus, there may be no feasible solution for a given instance of the minimum-cost flow problem.

If the first phase finds a feasible flow \(f\), the second phase transforms \(f\) into a minimum-cost flow. It checks whether the residual network \(G^f\) contains any negative cycle \(C\). If there is no such cycle, then \(f\) is a minimum-cost flow, by Lemma 6.3. Otherwise, the algorithm sends \(\delta\) units of flow along \(C\), where \(\delta\) is the minimum residual capacity of the edges in \(C\). The resulting flow \(f'\) is a feasible flow of lower cost than \(f\). Moreover, since sending \(\delta\) units of flow along \(C\) saturates at least one edge in \(C\), \(C\) is not a cycle in \(G^{f'}\)—\(C\) has been eliminated (or "cancelled"). This gives the algorithm its name: the negative cycle cancelling algorithm. Given the flow \(f'\), the algorithm continues to look for negative cycles in \(G^{f'}\) and cancels them until we obtain a flow whose residual network contains no such cycle.

Section 6.4.1 discusses the first phase of the algorithm, that is, how to find a feasible flow. Section 6.4.2 discusses the second phase of the algorithm. In particular, we need to figure out how to find negative cycles efficiently.