6.8.2. Simplified Capacity Scaling

In Section 6.6, every flow augmentation during the \(\Delta\)-phase of the capacity scaling algorithm sent \(\delta \ge \Delta\) units of flow from an excess node to a deficit node. In the repeated capacity scaling algorithm, we send exactly \(\Delta\) units of flow from an excess node to a deficit node, even if it would be possible to send more than \(\Delta\) units of flow between these two nodes. As the next lemma shows, this guarantees that the flow adjustment performed at the beginning of each phase becomes unnecessary because \(G^{f,\Delta} = G^f\) at all times. Corollary 6.45 below shows that this in turn implies that the total excess of all excess nodes is only \(2\Delta n\) in the \(\Delta\)-phase, in contrast to the \(2\Delta n + 4\Delta m\) bound achieved in the standard capacity scaling algorithm. This helps us to achieve a slightly better running time of \(O\bigl(n^2\lg n + nm\bigr)\) as opposed to \(O\bigl(nm\lg n + m^2\bigr)\) for each phase of the algorithm. We also no longer need to guarantee that \(\Delta\) is a power of \(2\) in each phase, so we simply set \(\Delta = C = \max_{x \in V}|b_x|\) in the first phase of the algorithm.

Lemma 6.44: If \(G\) is an uncapacitated network, then, during the \(\Delta\)-phase of the capacity scaling algorithm, every capacitated edge in \(G^f\) has residual capacity \(k\Delta\) for some \(k \in \mathbb{N}\). In particular, \(G^f = G^{f,\Delta}\). Moreover, every edge in \(G^f\) has non-negative reduced cost.

Proof: First observe that at the beginning of the first phase, \(G^f = G\), so every edge in \(G^f\) is uncapacitated. Thus, the first part of the lemma holds vacuously, and \(G^f = G^{f,\Delta}\) because every edge in \(G^f\) has infinite residual capacity. Since \(c_{x,y} \ge 0\) for every edge \((x,y) \in G\) and \(\pi_x = 0\) for every vertex \(x \in G\), we also have \(c^\pi_{x,y} = c_{x,y} = 0\) for every edge \((x,y) \in G^f = G\). Thus, the lemma holds at the beginning of the algorithm.

For any \(\Delta\)-phase other than the first phase, assume that the lemma holds at the end of the \(2\Delta\)-phase before it. Then \(G^f = G^{f,2\Delta} \subseteq G^{f,\Delta} \subseteq G^f\), so \(G^f = G^{f,\Delta}\). Since every capacitated edge in \(G^f\) has a residual capacity that is a multiple of \(2\Delta\), this capacity is clearly also a multiple of \(\Delta\). Finally, since transitioning from the \(2\Delta\)-phase to the \(\Delta\)-phase does not change \(G^f\), every edge in \(G^f\) continues to have a non-negative reduced cost. Thus, if the lemma holds at the end of the \(2\Delta\)-phase, it also holds at the beginning of the \(\Delta\)-phase.

It remains to prove that every flow augmentation during a given \(\Delta\)-phase maintains the invariant stated in the lemma.

Since the lemma holds at the beginning of the current \(\Delta\)-phase, every edge in \(G^f\) has a non-negative reduced cost at the beginning of this phase. Thus, there is no need to adjust the flow at the beginning of the phase, and all flow augmentations are "normal" flow augmentations, each of which sends exactly \(\Delta\) units of flow along some path \(P\) from an excess node to a deficit node.

After such an augmentation, every uncapacitated edge \((x,y) \in G^f\) such that \((x,y) \in P\) or \((y,x) \in P\) remains uncapacitated. If \((x,y)\) is a capacitated edge and \((x,y) \in P\), then its residual capacity changes from \(k\Delta\) to \((k-1)\Delta\), for some \(k \in \mathbb{N}\). If \((y,x) \in P\), then the new residual capacity is \((k+1)\Delta\). If neither \((x,y) \in P\) nor \((y,x) \in P\), then the residual capacity of \((x,y)\) does not change. Thus, every capacitated edge in \(G^f\) continues to have a capacity divisible by \(\Delta\) and \(G^f = G^{f,\Delta}\). Since we already proved that every augmentation applied by the capacity scaling algorithm maintains non-negative reduced costs for all edges in \(G^{f,\Delta}\), this shows that every edge in \(G^f\) has a non-negative reduced cost after the augmentation. ▨

Corollary 6.45: In an uncapacitated network, the total excess of all excess nodes during the \(\Delta\)-phase is less than \(2\Delta n\).

Proof: In the proof of Lemma 6.28, we showed that the total excess of all excess nodes at the beginning of the \(\Delta\)-phase is less than \(2\Delta n\). We observed in the proof of Lemma 6.44 that there is no need to adjust the flow at the beginning of any phase and that all flow augmentations are "normal" flow augmentations. Each such augmentation sends \(\Delta\) units of flow from an excess node with excess at least \(\Delta\) to a deficit node with deficit at least \(\Delta\) and thus does not increase the total excess of all excess nodes. ▨