6.9.6.1. Bounding the Number of Phases

We observed already in Corollary 6.63 that abundant components merge over time. The key to bounding the number of scaling phases is to show that it takes \(O(\lg n)\) scaling phases to decrease the number of abundant components by at least one. Thus, after \(O(n \lg n)\) scaling phases, there is only one abundant component left (unless the algorithm terminates before reducing the number of abundant components to one). When there is only one abundant component, there is also only one representative vertex and thus, by the Excess Invariant, at most one vertex with non-zero excess. However, since the total excess of all vertices is zero, the existence of a vertex with positive excess implies the existence of another vertex with negative excess and vice versa. This implies that once there is at most one vertex with non-zero excess left, there is in fact no vertex with non-zero excess left, so the algorithm exits.

Corollary 6.70 below proves this claim that it takes \(O(\lg n)\) scaling phases to reduce the number of abundant components by at least one. The proof of this corollary relies on the following lemma, which shows that the total supply balance of all nodes in an abundant component has a large absolute value if the excess of the representative of this component has a large absolute value.

Lemma 6.68: If \(\Bigl|e^{(i)}_{r_A}\Bigr| \ge \frac{\Delta^{(i)}}{4n}\) for the representative vertex \(r_A\) of an abundant component \(A\) in the \(i\)th scaling phase, then \(\bigl|\sum_{x \in A} b_x\bigr| \ge \frac{\Delta^{(i)}}{4n}\).

Proof: This clearly holds for \(i = 0\) because \(e^{(0)}_x = b_x\) for all \(x \in G\). So assume that \(i > 0\) and that \(\bigl|\sum_{x \in A} b_x\bigr| < \frac{\Delta^{(i)}}{4n}\). We prove that \(e^{(i)}_{r_A} = \sum_{x \in A} b_x\) in this case, so \(\Bigl|e^{(i)}_{r_A}\Bigr| < \frac{\Delta^{(i)}}{4n}\), and the lemma holds.

Since \(e^{(i)}_{r_A}\) is the excess of \(r_A\) at the end of the \((i-1)\)st scaling phase, we have \(\Bigl|e^{(i)}_{r_A}\Bigr| \le \bigl(1 - \frac{1}{n}\bigr)\Delta^{(i-1)}\) (because the \((i-1)\)st scaling phase ends only once no high-excess or high-deficit vertices remain). We also have

\[e^{(i)}_{r_A} = \sum_{x \in A} e^{(i)}_x = \sum_{x \in A} b_x - \sum_{x \in A} \sum_{y \notin A} \Bigl(f^{(i)}_{x,y} - f^{(i)}_{y,x}\Bigr),\]

that is,

\[\sum_{x \in A} \sum_{y \notin A} \Bigl(f^{(i)}_{x,y} - f^{(i)}_{y,x}\Bigr) = \sum_{x \in A} b_x - e^{(i)}_{r_A}\]

and

\[\Bigl|\sum_{x \in A} \sum_{y \notin A} \Bigl(f^{(i)}_{x,y} - f^{(i)}_{y,x}\Bigr)\Bigr| \le \Bigl|\sum_{x \in A} b_x\Bigr| + \Bigl|e^{(i)}_{r_A}\Bigr|.\]

Since \(\bigl|\sum_{x \in A} b_x\bigr| < \frac{\Delta^{(i)}}{4n}\), which is no more than \(\frac{\Delta^{(i-1)}}{8n}\), by Observation 6.59, and \(\Bigr|e^{(i)}_{r_A}\Bigr| \le \bigl(1 - \frac{1}{n}\bigr)\Delta^{(i-1)}\), this gives

\[\Bigl|\sum_{x \in A} \sum_{y \notin A}\ \Bigl(f^{(i)}_{x,y} - f^{(i)}_{y,x}\Bigr)\Bigr| \le \frac{\Delta^{(i-1)}}{8n} + \left(1 - \frac{1}{n}\right)\Delta^{(i-1)} < \Delta^{(i-1)}.\]

Since \(A\) is an abundant component in the \(i\)th scaling phase, every edge \((x,y)\) or \((y,x)\) with \(x \in A\) and \(y \notin A\) is non-abundant in the \(i\)th scaling phase. By Corollary 6.63, such an edge is also non-abundant in the \((i-1)\)st scaling phase. Thus, by the Flow Invariant, \(f^{(i)}_{x,y}\) and \(f^{(i)}_{y,x}\) are multiples of \(\Delta^{(i-1)}\). This implies that \(\sum_{x \in A} \sum_{y \notin A} \Bigl(f^{(i)}_{x,y} - f^{(i)}_{y,x}\Bigr)\) is also a multiple of \(\Delta^{(i-1)}\). Since \(\Bigl|\sum_{x \in A}\sum_{y \notin A} \Bigl(f^{(i)}_{x,y} - f^{(i)}_{y,x}\Bigr)\Bigr| < \Delta^{(i-1)}\), this implies that \(\sum_{x \in A}\sum_{y \notin A} \Bigl(f^{(i)}_{x,y} - f^{(i)}_{y,x}\Bigr) = 0\) and, thus, that \(e^{(i)}_{r_A} = \sum_{x \in A} b_x\), as claimed. ▨

The next lemma shows that once the representative of an abundant component \(A\) has excess at least \(\frac{\Delta^{(i)}}{4n}\), \(A\)'s days (or rather phases) are numbered: The component will survive only \(O(\lg n)\) more phases before either the algorithm exits or the component merges with another component to form a larger component. This will then almost immediately imply that after every \(O(\lg n)\) phases, the number of abundant components drops by at least one.

Lemma 6.69: Let \(t + 1\) be the number of scaling phases the enhanced capacity scaling algorithm executes. Let \(0 \le i \le t - 4 \lg n + 5\), and let \(A\) be an abundant component in the \(i\)th scaling phase with \(e^{(i)}_{r_A} \ge \frac{\Delta^{(i)}}{4n}\). Then \(A\) is not an abundant component in the \((i + 4 \lg n + 5)\)th scaling phase.

Proof: Let \(j = i + 4\lg n + 5\). By Observation 6.59, we have

\[\Delta^{(i)} \ge \Delta^{(j)} 2^{4 \lg n + 5} = 32\Delta^{(j)} n^4.\]

Since \(\Bigl|e^{(i)}_{r_A}\Bigr| \ge \frac{\Delta^{(i)}}{4n}\), Lemma 6.68 shows that

\[\bigl|\sum_{x \in A} b_x\bigr| \ge \frac{\Delta^{(i)}}{4n} \ge 8\Delta^{(j)}n^3.\]

By Lemma 6.60, the excess of \(r_A\) at the beginning of the \(j\)th scaling phase satisfies \(\Bigl|e^{(j)}_{r_A}\Bigr| < 2\Delta^{(j)}\). Thus,

\[\begin{aligned} e^{(j)}_{r_A} &= \sum_{x \in A} e^{(j)}_x\\ &= \sum_{x \in A} b_x - \sum_{x \in A} \sum_{y \notin A} \Bigl(f^{(j)}_{x,y} - f^{(j)}_{y,x}\Bigr)\\ \sum_{x \in A} \sum_{y \notin A} \Bigl(f^{(j)}_{x,y} - f^{(j)}_{y,x}\Bigr) &= \sum_{x \in A} b_x - e^{(j)}_{r_A}\\ \Bigl|\sum_{x \in A} \sum_{y \notin A} \Bigl(f^{(j)}_{x,y} - f^{(j)}_{y,x}\Bigr)\Bigr| &\ge \Bigl|\sum_{x \in A} b_x\Bigr| - \Bigl|e^{(j)}_{r_A}\Bigr|\\ &> 8\Delta^{(j)} n^3 - 2\Delta^{(j)}\\ &> 8\Delta^{(j)} n \cdot \binom{n}{2}. \end{aligned}\]

Since there are less than \(\binom{n}{2}\) pairs of vertices \((x,y)\) such that \(x \in A\) and \(y \notin A\), this implies that there exists such a pair that satisfies \(\Bigl|f^{(j)}_{x,y} - f^{(j)}_{y,x}\Bigr| > 8\Delta^{(j)} n\). Thus, since \(f^{(j)}_{x,y} \ge 0\) and \(f^{(j)}_{y,x} \ge 0\), at least one of \(f^{(j)}_{x,y}\) or \(f^{(j)}_{y,x}\) is at least \(8\Delta^{(j)} n\), that is, the edge \((x,y)\) or the edge \((y,x)\) is abundant in the \(j\)th scaling phase. This proves that \(A\) is not an abundant component in the \(j\)th scaling phase. ▨

Corollary 6.70: Let \(t + 1\) be the number of scaling phases the enhanced capacity scaling algorithm executes. For \(0 \le i \le t - 4 \lg n + 5\), the number of abundant components in the \((i + 4\lg n + 5)\)th scaling phase is less than the number of abundant components in the \(i\)th scaling phase.

Proof: Let \(A\) be the abundant component in the \(i\)th scaling phase whose representative has the highest absolute excess, that is, \(\Bigl|e^{(i)}_{r_A}\Bigr| = \max_{x \in V} \Bigl|e^{(i)}_x\Bigr|\). Then, by the choice of \(\Delta^{(i)}\), \(\Bigl|e^{(i)}_{r_A}\Bigr| \ge \frac{\Delta^{(i)}}{4n}\). Thus, by Lemma 6.69, \(A\) is not a component in the \((i + 4\lg n + 5)\)th scaling phase, that is, the number of abundant components in the \((i + 4\lg n + 5)\)th scaling phase is less than the number of abundant components in the \(i\)th scaling phase. ▨

As argued above, Corollary 6.70 implies

Corollary 6.71: The enhanced capacity scaling algorithm runs for \(O(n \lg n)\) phases.