6.9.6.2. Bounding the Number of Flow Augmentations

By Corollary 6.71, the number of scaling phases the enhanced capacity scaling algorithm executes is \(O(n \lg n)\). Lemmas 6.72 and 6.74 below show that the number of flow augmentations across all of these phases is also \(O(n \lg n)\).

Lemma 6.72: The enhanced capacity scaling algorithm performs less than \(n\) repair augmentations.

Proof: We perform a repair augmentation between two vertices \(x\) and \(y\) only when one of them, say \(x\), ceases to be a representative vertex. Since there are \(n\) representative vertices at the beginning of the algorithm and the algorithm does not create new representative vertices, this proves that there are at most \(n-1\) repair augmentations. ▨

The next lemma will be used in the proof of Lemma 6.74:

Lemma 6.73: The enhanced capacity scaling algorithm creates at most \(2n - 1\) abundant components.

Proof: Let us call an abundant component alive if it is an abundant component in the current scaling phase. The algorithm starts with each vertex in its own abundant component. These are the first \(n\) abundant components we create. Any other abundant component is created by merging two or more alive abundant components, which cease to be alive after the merge. Thus, every time we create a new abundant component, the number of alive abundant components drops by at least one. Since the number of alive abundant components is at least \(1\) at all times, this shows that we create at most \(n - 1\) abundant components in addition to the \(n\) abundant components created at the beginning of the algorithm. Thus, the algorithm creates at most \(2n - 1\) abundant components in total. ▨

In the remainder of this section, we call an abundant component \(A'\) a child of another abundant component \(A\) if \(A\) is produced by merging two or more smaller abundant components and \(A'\) is one of these smaller components. We use \(d_A\) to refer to the number of children of \(A\). Each of the \(n\) initial abundant components has no children, while every subsequent abundant component has at least two children.

Lemma 6.74: The enhanced capacity scaling algorithm performs \(O(n \lg n)\) regular flow augmentations.

Proof: We charge each regular flow augmentation to an abundant component so that, on average, every abundant component is charged for \(O(\lg n)\) regular flow augmentations. By Lemma 6.73, this shows that there are \(O(n \lg n)\) regular flow augmentations.

Paying for regular flow augmentations: Every regular flow augmentation has at least one endpoint \(x\) that is a high-excess or high-deficit vertex. If the augmentation sends flow from a high-excess vertex to a high-deficit vertex, we choose \(x\) arbitrarily from these two endpoints. By the Excess Invariant, \(x\) must be the representative \(r_A\) of some alive abundant component \(A\). We charge this augmentation to \(A\). In each scaling phase, we assign a budget of regular flow augmentations to each abundant component \(A\). We use \(\beta^{(i)}_A\) to refer to the budget assigned to \(A\) in the \(i\)th scaling phase. We prove that

• If \(A\) has \(d_A\) children, then its total budget across all phases is \(\sum_{i=0}^t \beta^{(i)}_A = O(\lg n) + 2d_A\).

• For all \(0 \le i \le t\), the number of regular flow augmentations charged to \(A\) in the \(i\)th scaling phase does not exceed \(\beta^{(i)}_A\).

Since we have just shown that there are at most \(2n - 1\) abundant components, and every abundant component is a child of at most one abundant component, this implies that the number of regular flow augmentations is at most

\[(2n - 1)O(\lg n) + 2(2n - 1) = O(n \lg n).\]

A component's budget: If \(A\) is not alive in the \(i\)th scaling phase, then \(\beta^{(i)}_A = 0\). Otherwise, let

\[\gamma^{(i)}_A = \left\lfloor\frac{\Bigl|e^{(i)}_{r_A}\Bigr|}{(1 - 1/n)\Delta^{(i)}}\right\rfloor.\]

If \(i > 0\) and \(A\) was alive also in the \((i-1)\)st phase, then \(\beta^{(i)}_A = \gamma^{(i)}_A\). If \(i = 0\) or \(A\) was not alive in the \((i-1)\)st phase, that is, if \(A\) is created at the beginning of the \(i\)th phase, then \(\beta^{(i)}_A = \gamma^{(i)}_A + 2d_A\). Thus,

\[\sum_{i=0}^t \beta^{(i)}_A = \sum_{i=0}^t \gamma^{(i)}_A + 2d_A\]

and, to prove that \(\sum_{i=0}^t \beta^{(i)}_A = O(\lg n) + 2d_A\), it suffices to show that \(\sum_{i=0}^t \gamma^{(i)}_A = O(\lg n)\).

If \(\gamma^{(i)}_A = 0\) for all \(0 \le i \le t\), then this is clearly true. So assume that there exists an index \(i\) such that \(\gamma^{(i)}_A > 0\), let \(h\) be the index of the first phase such that \(\gamma^{(h)}_A > 0\), and let \(j\) be the index of the last phase such that \(\gamma^{(j)}_A > 0\).

Since \(\gamma^{(h)}_A > 0\), we have

\[\Bigl|e^{(h)}_{r_A}\Bigr| \ge \left(1 - \frac{1}{n}\right)\Delta^{(h)} \ge \frac{\Delta^{(h)}}{4n}.\]

Thus, by Lemma 6.69, either \(t < h + 4\lg n + 5\) or \(A\) is no longer alive in the \((h + 4\lg n + 5)\)th scaling phase.

Since \(\gamma^{(i)}_A = 0\) in any phase during which \(A\) is not alive, this shows that \(j < h + 4\lg n + 5\), that is, \(j - h = O(\lg n)\).

For every phase \(i\), we have \(\Bigl|e^{(i)}_{r_A}\Bigr| \le 2\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\), by Lemma 6.60, so \(\biggl\lfloor\frac{\bigl|e^{(i)}_{r_A}\bigr|}{(1 - 1/n)\Delta^{(i)}}\biggr\rfloor \le 2\). Thus,

\[\sum_{i=0}^t \gamma^{(i)}_A = \sum_{i=h}^j \gamma^{(i)}_A \le 2(j - h + 1) = O(\lg n).\]

Paying for augmentations without breaking the bank: To prove that no abundant component \(A\) is charged for more than \(\beta^{(i)}_A\) regular flow augmentations in the \(i\)th scaling phase, consider an arbitrary such phase and an arbitrary component \(A\).

If \(A\) is not alive in the \(i\)th scaling phase, then it is also not charged for any flow augmentation in this phase, so its budget of \(\beta^{(i)}_A = 0\) flow augmentation is not exceeded.

If \(A\) is alive, then consider \(r_A\)'s excess \(e_{r_A}\) immediately after the last repair augmentation in the \(i\)th phase. Assume w.l.o.g. that \(e_{r_A}\) is positive. By Observation 6.58, no regular flow augmentation in the \(i\)th phase that has \(r_A\) as an endpoint turns \(r_A\) into a high-deficit vertex. By the same observation, once \(r_A\) ceases to be a high-excess vertex in the \(i\)th phase (if it had high excess to begin with), it does not become a high-excess vertex again in this phase. Thus, if there are \(k\) regular flow augmentations with \(r_A\) as a high-excess endpoint, then \(r_A\) remains a high-excess vertex after the first \(k - 1\) of them and \(A\) is charged for at most \(k\) augmentations. Therefore, we need to prove that \(\beta^{(i)}_A \ge k\).

Every flow augmentation from a high-excess vertex \(x\) to an active deficit vertex \(y\) after which \(x\) remains an excess vertex decreases \(e_x\) by \(\Delta^{(i)}\). Since \(r_A\) has high excess after the \((k - 1)\)st flow augmentation that has \(r_A\) as a high-excess endpoint, we therefore have

\[e_{r_A} \ge \left(1 - \frac{1}{n}\right)\Delta^{(i)} + (k - 1)\Delta^{(i)} > k\left(1 - \frac{1}{n}\right)\Delta^{(i)}\]

before the first such flow augmentation.

To prove that \(\beta^{(i)}_A \ge k\), it therefore suffices to prove that \(\beta^{(i)}_A \ge \Bigl\lfloor \frac{|e_{r_A}|}{(1 - 1/n)\Delta^{(i)}} \Bigr\rfloor\).

If \(A\) has no children or \(A\) was alive also in the \((i - 1)\)st phase, then the repair augmentations at the beginning of the \(i\)th phase do not alter \(e_{r_A}\), so \(e_{r_A} = e^{(i)}_{r_A}\) and

\[\beta^{(i)}_A = \gamma^{(i)}_A = \left\lfloor\frac{\Bigl|e^{(i)}_{r_A}\Bigr|}{(1 - 1/n)\Delta^{(i)}}\right\rfloor = \left\lfloor\frac{|e_{r_A}|}{(1 - 1/n)\Delta^{(i)}}\right\rfloor.\]

If \(A\) has at least two children and is created in the \(i\)th scaling phase, then observe that \(r_A\) is the endpoint of \(d_A - 1\) repair augmentations. Each such augmentation moves the excess \(e^{(i)}_{r_{A'}}\) of the representative \(r_{A'}\) of some child \(A'\) of \(A\) to \(r_A\). By Lemma 6.60, \(\Bigl|e^{(i)}_{r_{A'}}\Bigr| \le 2\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\), so each such augmentation changes \(e_{r_A}\) by at most \(2\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\). Therefore,

\[|e_{r_A}| \le \Bigl|e^{(i)}_{r_A}\Bigr| + 2(d_A - 1)\left(1 - \frac{1}{n}\right)\Delta^{(i)}\]

and

\[\begin{aligned} \beta^{(i)}_A &= \left\lfloor\frac{\Bigl|e^{(i)}_{r_A}\Bigr|}{(1 - 1/n)\Delta^{(i)}}\right\rfloor + 2d_A\\ &= \left\lfloor\frac{\Bigl|e^{(i)}_{r_A}\Bigr| + 2d_A(1 - 1/n)\Delta^{(i)}}{(1 - 1/n)\Delta^{(i)}}\right\rfloor\\ &> \left\lfloor\frac{|e_{r_A}|}{(1 - 1/n)\Delta^{(i)}}\right\rfloor. \end{aligned}\]

This finishes the proof. ▨