6.9.5. Correctness of the Algorithm

The correctness of the enhanced capacity scaling algorithm follows almost immediately from the Flow Invariant and Excess Invariant. We prove that the algorithm returns a minimum-cost flow if it returns anything at all, that is, if it terminates. The bound on the algorithm's running time in Section 6.9.6 implies that it does terminate.

Lemma 6.66 below proves that the edge labelling \(f\) maintained by the enhanced capacity scaling algorithm is a pseudo-flow at all times. Since the algorithm exits only once \(f\) satisfies flow conservation, \(f\) is thus a flow when the algorithm returns. Lemma 6.67 then shows that the edge labelling \(f\) and the potential function \(\pi\) satisfy the reduced cost optimality criterion from Lemma 6.2. Thus, once \(f\) is a flow—that is, once the algorithm terminates—\(f\) is a minimum-cost flow.

Lemma 6.66: The edge labelling \(f\) is a pseudo-flow at all times.

Proof: First observe that increasing the flow along an edge \(e \in G\) never violates its capacity constraint because \(u_e = \infty\). Thus, we only need to verify that every edge carries a non-negative amount of flow at all times.

For an abundant edge \(e \in G\), Corollary 6.63 shows that its flow remains strictly positive after this edge becomes abundant.

For a non-abundant edge \((x,y) \in G\), observe that \(f_{x,y}\) can change only due to regular flow augmentations because repair augmentations use only abundant edges. If such an augmentation decreases \(f_{x,y}\), then \((y,x) \in G^f\). By Corollary 6.65, \(f_{x,y} = c^f_{y,x} \ge \Delta^{(i)}\) before the augmentation. Thus, decreasing \(f_{x,y}\) by \(\Delta^{(i)}\) keeps \(f_{x,y}\) non-negative. ▨

Lemma 6.67: The edge labelling \(f\) and potential function \(\pi\) maintained by the enhanced capacity scaling algorithm satisfy the reduced cost optimality criterion at all times.

Proof: Since \(f^{(0)}_e = 0\) for every edge \(e \in G\), we have \(G^f = G\) at the beginning of the algorithm. Since every edge in \(G\) has a non-negative cost and \(\pi^{(0)}_x = 0\) for every vertex \(x \in G\), this implies that \(c^\pi_e \ge 0\) for every edge \(e \in G^f\) at the beginning of the algorithm. Thus, the reduced cost optimality criterion is satisfied initially.

Now consider the effect of flow augmentations. Regular flow augmentations first. Each such augmentation sends flow along a shortest path in \(G^f\). As shown in the correctness proof of the successive shortest paths algorithm, this maintains reduced cost optimality.

A repair augmentation uses only abundant edges in \(G^f\). By Corollary 6.63, a repair augmentation never reduces the flow along an abundant edge to zero. Thus, \(G^f\) does not change as a result of a repair augmentation and, by leaving \(\pi\) unchanged, we ensure that the reduced cost optimality criterion continues to be met. ▨