6.9.3. Detailed Algorithm Description

We are now ready to give a detailed description of the enhanced capacity scaling algorithm. As the successive shortest paths algorithm and the capacity scaling algorithm, we start with the trivial flow \(f\) defined as \(f_{x,y} = 0\) for all \((x,y) \in G\) and with the trivial potential function defined as \(\pi_x = 0\) for all \(x \in G\). Then we proceed in scaling phases, just as the capacity scaling algorithm. Each phase performs the following steps:

• The \(i\)th scaling phase starts by choosing \(\Delta^{(i)}\). In the first phase (\(i = 0\)), we set \(\Delta^{(0)} = \max_{x \in V}|b_x|\). In any other phase, if there exists a vertex \(x\) with absolute excess \(\Bigl|e^{(i)}_x\Bigr| \ge \frac{\Delta^{(i-1)}}{8n}\), then we set \(\Delta^{(i)} = \frac{\Delta^{(i-1)}}{2}\), as in the capacity scaling algorithm. If there is no such vertex, then \(\Delta^{(i)} = \max_{x \in V}\Bigl|e^{(i)}_x\Bigr|\).

  Observation 6.59: For all \(i > 1\), \(\Delta^{(i)} \le \frac{\Delta^{(i-1)}}{2}\).

  Proof: If \(\Delta^{(i)} = \frac{\Delta^{(i-1)}}{2}\), the observation is obviously true. If \(\Delta^{(i)} = \max_{x \in V} \Bigl|e^{(i)}_x\Bigr|\), then \(\max_{x \in V} |e^{(i)}_x| < \frac{\Delta^{(i-1)}}{8n}\), so \(\Delta^{(i)} < \frac{\Delta^{(i-1)}}{8n} < \frac{\Delta^{(i-1)}}{2}\). ▨

• Next we identify abundant edges and abundant components based on the chosen value of \(\Delta^{(i)}\).

• Next we restore the Excess Invariant based on the new abundant components.

  In the first phase, we have \(f^{(0)}_{x,y} = 0\) for all \((x,y) \in G\), so there are no abundant edges. Thus, every vertex is in its own abundant component and is the representative of this component. The Excess Invariant holds trivially in this case.

  As already mentioned, we will show, in Corollary 6.63, that abundant components merge over time.

  If an abundant component \(A\) in the \(i\)th phase was also an abundant component in the \((i-1)\)st phase, then only its representative has non-zero excess, by the Excess Invariant at the end of the \((i-1)\)st phase. Thus, the Excess Invariant continues to hold for \(A\).

  If \(A\) is the result of merging at least two abundant components \(A_1, \ldots, A_k\) from the \((i-1)\)st phase, then we choose its representative \(r_A\) to be the same as \(r_{A_1}\). The other representatives \(r_{A_2}, \ldots, r_{A_k}\) become non-representatives. To restore the Excess Invariant, we need to reduce their excesses to \(0\).

  For each such vertex \(r_{A_j}\), we move \(e^{(i)}_{r_{A_j}}\) units of flow from \(r_{A_j}\) to \(r_A\) if \(e^{(i)}_{r_{A_j}} > 0\), or we move \(-e^{(i)}_{r_{A_j}}\) units of flow from \(r_A\) to \(r_{A_j}\) if \(e^{(i)}_{r_{A_j}} < 0\). In other words, we pool the total excess of the former representatives \(r_{A_1}, \ldots, r_{A_k}\) at the single representative \(r_A\). Since these flow augmentations serve the purpose of repairing the Excess Invariant after merging abundant components, we call these flow augmentations repair augmentations. These augmentations are special in that they use only abundant edges in \(A\). Corollary 6.62 shows that the abundant edges in \(A\) have sufficient residual capacity for all these repair augmentations.

• The remainder of the \(i\)th scaling phase has the goal to eliminate all high-excess and high-deficit vertices. As soon as there is no high-excess and no high-deficit vertex left, the \(i\)th scaling phase ends.¹ If all vertices have excess \(0\) at this point, the algorithm terminates and returns the current flow \(f\). We prove in Section 6.9.5 that \(f\) is a minimum-cost flow in \(G\) at this point. If there are still vertices with non-zero excess, we start another phase.

  As long as \(G\) contains a high-excess vertex, we choose such a vertex \(x\). By Observation 6.57, there also exists an active deficit vertex \(y\) in this case. We compute a shortest path \(P\) from \(x\) to \(y\) in \(G^f\), as well as the distances from \(x\) to all vertices in \(G^f\), with respect to the reduced edge costs \(c^\pi_{x,y}\). By Corollary 6.65, every edge on this path has residual capacity at least \(\Delta^{(i)}\). Thus, we can move \(\Delta^{(i)}\) units of flow from \(x\) to \(y\) along \(P\) while maintaining that \(f\) is a pseudo-flow.

  As in all variants of the successive shortest paths algorithm, we decrease every vertex's potential by its distance from \(x\) to maintain reduced cost optimality.

  If there is a high-deficit vertex but no high-excess vertex, we choose \(y\) to be a high-deficit vertex and \(x\) to be an active excess vertex, and we once again move \(\Delta^{(i)}\) units of flow along a shortest path from \(x\) to \(y\) and decrease every vertex's potential by its distance from \(x\).

  We continue doing this until there are no high-excess and no high-deficit vertices left, at which point the \(i\)th scaling phase ends. Since these flow augmentations performed after restoring the Excess Invariant serve the main purpose of the algorithm—making progress towards flow conservation—we call them regular flow augmentations.

This is the complete description of the enhanced capacity scaling algorithm. It remains to establish its correctness and to bound its running time. We divide this task into three parts. First, in Section 6.9.4, we prove that the algorithm maintains the Excess Invariant and the Flow Invariant. Then, in Section 6.9.5, we use this to establish the correctness of the algorithm. Finally, in Section 6.9.6, we analyze the running time of the algorithm.