6.9.6.3. Putting Things Together

We are ready to summarize the result of this section:

Theorem 6.75: The enhanced capacity scaling algorithm computes a minimum-cost flow in an uncapacitated network in \(O((n \lg n + m)n \lg n)\) time. For a capacitated network, its running time is \(O((n \lg n + m)m \lg n)\).

Proof: By Lemmas 6.66 and 6.67, \(f\) is a pseudo-flow at all times and \(f\) and \(\pi\) satisfy the reduced cost optimality criterion. Since the algorithm exits only once \(f\) also satisfies flow conservation, that is, once \(f\) is a flow, Lemma 6.2 shows that \(f\) is a minimum-cost flow once the algorithm exits.

On an uncapacitated network, the algorithm runs for \(O(n \lg n)\) scaling phases and performs less than \(n\) repair augmentations and \(O(n \lg n)\) regular flow augmentations.

Each phase starts by computing the abundant components, which is easily done in \(O(m)\) time by inspecting all edges of \(G\) to decide which ones are abundant, and then computing the connected components of the subgraph containing only these edges. The cost of this step across all phases is thus \(O(nm \lg n)\).

The cost of each repair augmentation is dominated by the cost of finding a path in the abundant subgraph from a newly non-representative vertex \(r_{A'}\) to the representative \(r_A\) of the abundant component \(A\) that contains \(r_{A'}\). This is easily done in \(O(m)\) time using breadth-first search or depth-first search. The cost of all repair augmentations is thus \(O(nm)\).

Similarly to the successive shortest paths algorithm or the capacity scaling algorithm, the cost of a regular flow augmentation is dominated by the cost of finding a shortest path from a high-excess vertex \(x\) to an active deficit vertex \(y\) or from an active excess vertex \(x\) to a high-deficit vertex \(y\), along with the distances of all vertices from \(x\). Since we use the reduced edge costs as edge lengths and the algorithm maintains reduced cost optimality, by Lemma 6.67, all edges have non-negative lengths, so we can find the path from \(x\) to \(y\) and the distances from \(x\) using Dijkstra's algorithm, which takes \(O(n \lg n + m)\) time. The cost of all regular flow augmentations is thus \(O((n \lg n + m)n \lg n)\). Since this dominates the cost of computing abundant components and the cost of all repair augmentations, the cost of the whole algorithm is thus \(O((n \lg n + m)n \lg n)\).

If the edges in the network have finite capacities initially, then we can make the network uncapacitated using the transformation in Section 6.3.3. This increases the number of vertices to \(O(m)\). By Exercise 6.3, computing the distances from any vertex in the resulting network to all other vertices using Dijkstra's algorithm still takes \(O(n \lg n + m)\) time. Thus, the cost on a network with edge capacities is \(O((n \lg n + m)m \lg m) = O((n \lg n + m)m \lg n)\). ▨