6.9.4. Maintenance of the Flow and Excess Invariants

We have argued already that the Excess Invariant holds at the beginning of the first phase. At the beginning of every subsequent phase, we explicitly eliminate the excess or deficit of vertices that have become non-representative by moving their excess or deficit to a representative vertex along a path of abundant edges. Thus, we explicitly establish the Excess Invariant at the beginning of each phase.

The regular flow augmentations in each phase cannot lead to a violation of the Excess Invariant because they move flow only between active vertices, which must be representative vertices. Thus, as far as the maintenance of the Excess Invariant is concerned, we only need to prove that we can restore it at the beginning of each phase by moving flow from newly non-representative vertices to representative vertices along paths composed of abundant edges. Corollary 6.62 below proves this.

To prove Corollary 6.62, we need two auxiliary results. Lemma 6.60 establishes an upper bound on the absolute excess of every vertex at the beginning of a phase. Lemma 6.61 proves that this implies that the total amount of flow sent between vertices in each phase is bounded. This implies that abundant edges have sufficient residual capacity to accommodate all repair augmentations and that abundant edges remain abundant in all subsequent phases. These results are also sufficient to prove that the algorithm maintains the Flow Invariant, which we prove in Lemma 6.64.

Lemma 6.60: Every vertex \(x \in G\) satisfies \(\Bigl|e^{(i)}_x\Bigr| \le 2\bigl(1-\frac{1}{n}\bigr)\Delta^{(i)}\) and \(\Bigl|e^{(i+1)}_x\Bigr| \le \bigl(1-\frac{1}{n}\bigr)\Delta^{(i)}\).

Proof: The bound on \(\Bigl|e^{(i+1)}_x\Bigr|\) follows immediately because the \(i\)th scaling phase ends only once there are no high-excess and no high-deficit vertices left, that is, once every vertex satisfies \(|e_x| \le \bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\).

To bound \(\Bigl|e^{(i)}_x\Bigr|\), we can assume that there are at least two vertices because otherwise even the initial flow \(f^{(0)}\) is a minimum-cost flow and the algorithm exits immediately. Thus, if \(\Delta^{(i)} = \max_{y \in V} \Bigl|e^{(i)}_y\Bigr|\), then \(\Bigl|e^{(i)}_x\Bigr| \le \Delta^{(i)} \le 2\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\).

If \(\Delta^{(i)} \ne \max_{y \in V} \Bigl|e^{(i)}_y\Bigr|\), then \(i > 1\) and \(\Delta^{(i)} = \frac{\Delta^{(i-1)}}{2}\). By applying the lemma to the \((i-1)\)st scaling phase, we obtain that \(\Bigl|e^{(i)}_x\Bigr| \le \bigl(1 - \frac{1}{n}\bigr)\Delta^{(i-1)} = 2\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\). ▨

Lemma 6.61: At all times during the \(i\)th scaling phase, \(\Bigl|f_e - f^{(i)}_e\Bigr| < 4\Delta^{(i)} n\), for every edge \(e \in G\).

Proof: There are two types of augmentations performed during the \(i\)th scaling phase: repair augmentations and regular flow augmentations.

Since there are at most \(n-1\) representative vertices that become non-representative vertices at the beginning of the \(i\)th scaling phase, the \(i\)th scaling phase performs at most \(n-1\) repair augmentations. Since the excess \(e^{(i)}_x\) of every vertex \(x\) satisfies \(\Bigl|e^{(i)}_x\Bigr| \le 2\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\), by Lemma 6.60, each such augmentation changes the flow along any edge by less than \(2\Delta^{(i)}\). Summing over all repair augmentations, the flow along any edge changes by less than \(2\Delta^{(i)} n\).

Next observe that the repair augmentations in the \(i\)th scaling phase do not increase the total absolute excess of all vertices. Indeed, each such augmentation eliminates the excess \(e^{(i)}_{r_{A_j}}\) of some representative vertex and increases the excess of another representative vertex \(r_A\) by \(e^{(i)}_{r_{A_j}}\). If \(r_A\) and \(r_{A_j}\) are both excess or both deficit vertices, then \(|e_{r_A}|\) increases by exactly \(\Bigl|e^{(i)}_{r_{A_j}}\Bigr|\). Otherwise, \(|e_{r_A}|\) increases by at most \(\Bigl|e^{(i)}_{r_{A_j}}\Bigr|\). This proves that, after all repair augmentations in the \(i\)th scaling phase, \(\sum_{x \in V} |e_x| \le \sum_{x \in V} \Bigl|e^{(i)}_x\Bigr| \le 2n\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)} = 2\Delta^{(i)}(n-1)\).

Let \(X \le 2\Delta^{(i)}(n-1)\) be the total absolute excess of all high-excess and high-deficit vertices after all repair augmentations in the \(i\)th scaling phase. We prove that every regular flow augmentation during the \(i\)th scaling phase decreases \(X\) by at least \(\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\). Thus, there are at most \(\frac{2\Delta^{(i)}(n - 1)}{(1 - 1/n)\Delta^{(i)}} = 2n\) regular flow augmentations in the \(i\)th scaling phase. Since each such augmentation pushes \(\Delta^{(i)}\) units of flow from an excess vertex to a deficit vertex, the regular augmentations in the \(i\)th scaling phase change the flow along any edge by at most \(2\Delta^{(i)} n\). Since the repair augmentations change the flow along any edge \(e\) by less than \(2\Delta^{(i)} n\), this shows that \(\Bigl|f_e - f^{(i)}_e\Bigr| < 4\Delta^{(i)} n\) at any time during the \(i\)th scaling phase.

So consider a regular flow augmentation and assume that it sends \(\Delta^{(i)}\) units of flow from a high-excess vertex \(x\) to an active deficit vertex \(y\). The case when \(x\) is an active excess vertex and \(y\) is a high-deficit vertex is similar.

Since \(x\) is a high-excess vertex, its excess before the augmentation is \(e_x > \bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\). After the augmentation, its excess is \(e_x - \Delta^{(i)}\). If \(e_x \ge \Delta^{(i)}\), then \(|e_x| - \Bigl|e_x - \Delta^{(i)}\Bigr| = \Delta^{(i)}\), that is, \(x\)'s contribution to \(X\) is decreased by at least \(\Delta^{(i)}\) even if \(x\) remains a high-excess vertex. If \(e_x < \Delta^{(i)}\), then \(e_x - \Delta^{(i)} < 0\), so \(x\) becomes a deficit vertex but not a high-deficit vertex, by Observation 6.58. Since its excess before the augmentation was greater than \(\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\), the augmentation thus decreases \(x\)'s contribution to \(X\) by more than \(\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\).

Analogously, \(y\)'s contribution to \(X\) is decreased by \(\Delta^{(i)}\) if \(e_y \le -\Delta^{(i)}\). If \(e_y > -\Delta^i\), then \(y\) ceases to be a deficit vertex after the augmentation and, by Observation 6.58, does not become a high-excess vertex. Thus, its contribution to \(X\) does not increase. Overall, the change in \(x\) and \(y\)'s contributions to \(X\) results in a decrease of \(X\) by at least \(\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\). This finishes the proof. ▨

Now consider any abundant edge \(e\) in the \(i\)th scaling phase. By Lemma 6.61, we have \(\Bigl|f_e - f^{(i)}_e\Bigr| < 4\Delta^{(i)}n\). Since \(e\) is abundant, we have \(f^{(i)}_e \ge 8\Delta^{(i)}n\), so \(f_e \ge 4\Delta^{(i)}n > 0\) at any time during the \(i\)th scaling phase. This immediately implies the following two corollaries:

Corollary 6.62: When an abundant component \(A\) in the \(i\)th scaling phase is produced by merging at least two abundant components \(A_1, \ldots, A_k\) from the \((i-1)\)st scaling phase, the abundant edges in \(A\) have sufficient residual capacity to move the excesses of \(r_{A_2}, \ldots, r_{A_k}\) to \(r_A = r_{A_1}\).

Proof: Consider an abundant edge in \(A\).

Every edge \((x,y) \in G^f\) such that \((x,y) \in G\) has infinite residual capacity because \(G\) is uncapacitated. Thus, we cannot move sufficient flow along \((x,y)\) to exceed its capacity.

If \((y,x) \in G\), then moving flow along \((x,y)\) decreases \(f_{y,x}\). Since \((x,y)\) is abundant, we have \(f^{(i)}_{y,x} \ge 8\Delta^{(i)}n\). By Lemma 6.61, all augmentations in the \(i\)th scaling phase, including repair augmentations and regular augmentations, move at most \(4\Delta^{(i)}n\) units of flow along any edge. Thus, \(f_{y,x}\) remains strictly positive. ▨

Corollary 6.63: If an edge \(e\) is abundant in the \(i\)th scaling phase, then it is abundant also in the \(j\)th scaling phase for any \(j \ge i\). In particular, every abundant component in the \(i\)th phase is a subgraph of an abundant component in the \(j\)th phase for any \(j \ge i\).

Proof: The argument in the proof of Corollary 6.62 shows that an edge \(e\) that is abundant in the \(i\)th phase satisfies \(\bigl|f^{(i+1)}_e\bigr| \ge 4\Delta^{(i)} n\) at the end of the \(i\)th phase. By Observation 6.59, \(\Delta^{(i+1)} \le \frac{\Delta^{(i)}}{2}\). Thus, \(\bigl|f^{(i+1)}_e\bigr| \ge 8\Delta^{(i+1)} n\), and \(e\) is abundant also in the \((i+1)\)st phase. The claim now follows by induction. ▨

The last lemma in this subsection shows that the enhanced capacity scaling algorithm maintains the Flow Invariant.

Lemma 6.64: The enhanced capacity scaling algorithm maintains the Flow Invariant.

Proof: The invariant holds at the beginning of the algorithm because \(f^{(0)}_e = 0\) for every edge \(e \in G\). Thus, the invariant can be violated only as a result of flow augmentations and changes to \(\Delta\) at the beginning of different scaling phases.

Any repair augmentation changes only the flow along abundant edges. By Corollary 6.63, these edges remain abundant throughout the remainder of the algorithm, so changing the flow along these edges cannot violate the Flow Invariant.

Any regular augmentation in the \(i\)th scaling phase sends \(\Delta^{(i)}\) units of flow along some path in \(G^f\). This changes the flow along any edge in \(G\) by \(\pm\Delta^{(i)}\) and thus maintains the Flow Invariant.

Finally, consider the effect of decreasing \(\Delta\). An edge \(e\) can violate the Flow Invariant at the beginning of the \(i\)th scaling phase only if \(f^{(i)}_e > 0\) and \(e\) is non-abundant in the \(i\)th scaling phase. By Corollary 6.63, this implies that \(e\) is non-abundant also in the \((i-1)\)st scaling phase. Thus, by the Flow Invariant applied to the \((i-1)\)st phase and since \(f^{(i)}_e > 0\), we have \(f^{(i)}_e = k\Delta^{(i-1)}\) for some \(k \in \mathbb{N}, k \ge 1\). In particular, \(f^{(i)}_e \ge \Delta^{(i-1)}\).

If \(\Delta^{(i)} = \frac{\Delta^{(i-1)}}{2}\), then \(f^{(i)}_e = k\Delta^{(i-1)} = 2k\Delta^{(i)}\), so \(e\) does not violate the Flow Invariant at the beginning of the \(i\)th phase.

If \(\Delta^{(i)} = \max_{x \in V}\Bigl|e^{(i)}_x\Bigr|\), then \(\Delta^{(i)} < \frac{\Delta^{(i-1)}}{8n}\). Thus, \(f^{(i)}_e \ge \Delta^{(i-1)} > 8\Delta^{(i)}n\) and \(e\) is abundant in the \(i\)th scaling phase, a contradiction because we assumed that \(i\) is non-abundant in the \(i\)th scaling phase. ▨

An immediate corollary of the Flow Invariant is the following:

Corollary 6.65: During the \(i\)th scaling phase, every edge in \(G^f\) has residual capacity at least \(\Delta^{(i)}\).

Proof: Consider any edge \((x,y) \in G^f\). If \((x,y) \in G\), then \(u^f_{x,y} = \infty\), so the corollary holds for \((x,y)\).

If \((y,x) \in G\), then \(u^f_{x,y} = f_{y,x}\). If \((y,x)\) is abundant, then \(u^f_{x,y} = f_{y,x} \ge 4\Delta^{(i)}n > \Delta^{(i)}\), by Lemma 6.61. If \((y,x)\) is non-abundant, then \(f_{y,x}\) is a multiple of \(\Delta^{(i)}\), by the Flow Invariant. Since \((x,y) \in G^f\), we have \(f_{y,x} > 0\). Thus, \(u^f_{x,y} = f_{y,x} \ge \Delta^{(i)}\). ▨