6.6.2. Correctness of the Algorithm

I mentioned that the fact that the capacity scaling algorithm uses shortest paths is \(G^{f,\Delta}\) to update the current pseudo-flow during the \(\Delta\)-phase, and that the potential function \(\pi\) is updated using distances in \(G^{f,\Delta}\) has important implications. In a nutshell, it means that the capacity scaling algorithm does not maintain reduced cost optimality.

In this section, we state a weaker form of reduced cost optimality that the algorithm does maintain, as well a second invariant. We will argue that this weaker reduced cost optimality condition is the same as reduced cost optimality in the final phase of the algorithm, and that the second invariant implies that at the end of the final phase—the \(1\)-phase—there are no excess vertices and no deficit vertices left. Thus, we obtain a feasible flow that satisfies reduced cost optimality at the end of the last phase. By Lemma 6.2, this implies that the flow returned by the algorithm is a minimum-cost flow.

The weaker form of reduced cost optimality maintained during the \(\Delta\)-phase is

Invariant 6.23: For every edge \(e \in G^{f,\Delta}\), \(c^\pi_e \ge 0\).

The difference to Invariant 6.20 is that we provide no guarantee that any edge \(e \in G^f\) that is not in \(G^{f,\Delta}\) (any edge with residual capacity less than \(\Delta\)) satisfies \(c^\pi_e \ge 0\).

The other invariant the algorithm maintains is

Invariant 6.24: At the beginning of the \(\Delta\)-phase, every vertex has excess less than \(2\Delta\) or every vertex has excess greater than \(-2\Delta\). At the end of the \(\Delta\)-phase, every vertex has excess less than \(\Delta\) or every vertex has excess greater than \(-\Delta\).

As the next lemma shows, these two invariants imply that the algorithm computes a minimum-cost flow:

Lemma 6.25: At the end of the \(1\)-phase (the last phase) of the capacity scaling algorithm, \(f\) is a minimum-cost flow.

Proof: By Invariant 6.24, every vertex has excess less than \(1\) or every vertex has excess greater than \(-1\) at the end of the \(1\)-phase. Since the node supply balances and edge capacities are integral, the node excesses are also integral at all times. Thus, this implies that every vertex has non-positive excess or every vertex has non-negative excess.

Since \(\sum_{x \in G} b_x = 0\) (the total supply of all supply nodes matches the total demand of all demand nodes), we also have \(\sum_{x \in G^f} e_x = 0\). Thus, if all vertices have non-positive excess or all vertices have non-negative excess, we must have that all node excesses are \(0\) and \(f\) satisfies flow conservation. Since the algorithm ensures that \(f\) is a pseudo-flow, \(f\) also satisfies the capacity constraints and is thus a flow.

To see that \(f\) is a minimum-cost flow, observe once again that all edges in \(G^f\) have integral residual capacities because the edges of \(G\) have integral capacities and therefore, \(f\) is integral. Thus, any edge in \(G^f\) has residual capacity at least \(1\) and belongs to \(G^{f,1}\): \(G^{f,1} = G^f\). By Invariant 6.23, this implies that \(c^\pi_e \ge 0\) for every edge \(e \in G^f\), and \(f\) is a minimum-cost flow, by Lemma 6.2. ▨

It remains to prove that the capacity scaling algorithm does indeed maintain Invariants 6.23 and 6.24.