6.9.1. Abundant Edges and Components

One of the central concepts in the enhanced capacity scaling algorithm is that of an "abundant edge", an edge that carries a large amount of flow:

An edge \(e \in G\) is abundant in the \(i\)th scaling phase if it satisfies \(f^{(i)}_e \ge 8\Delta^{(i)} n\).

Recall that \(f^{(i)}\) refers to the flow function at the beginning of the \(i\)th scaling phase. We allow the flow along an abundant edge to drop below \(8\Delta^{(i)} n\) during the \(i\)th scaling phase. We still consider it abundant for the duration of the entire phase, based on the amount of flow it carried at the beginning of the phase.

The abundant subgraph of \(G\) is the subgraph of \(G\) with vertex set \(V\) and with the set of all abundant edges of \(G\) as its edge set.

An abundant component of \(G\) is a connected component of the abundant subgraph of \(G\).

Since the set of abundant edges may change from phase to phase, so do the abundant subgraph and the abundant components.

We extend the definitions of abundant edges, the abundant subgraph, and abundant components to the residual network \(G^f\) by considering an edge \((x,y) \in G^f\) to be abundant if either \((x,y) \in G\) and \((x,y)\) is abundant in \(G\) or \((y,x) \in G\) and \((y,x)\) is abundant in \(G\). The abundant subgraph and the abundant components of \(G^f\) are then defined analogously to the abundant subgraph and abundant components of \(G\).

Possibly the most important property of the enhanced capacity scaling algorithm that we prove in Corollary 6.63 is that once an edge becomes abundant at the beginning of some scaling phase, it remains abundant in all subsequent phases. Thus, the abundant subgraph of \(G\) only grows over time and abundant components merge over time to form fewer, larger abundant components.

We will show that it takes only \(O(\lg n)\) scaling phases to ensure that some abundant components merge, that is, that the number of abundant components decreases by at least one. Moreover, we will show that once there is only one abundant component left, the current pseudo-flow \(f\) is in fact a minimum-cost flow. Thus, it takes at most \(O(n \lg n)\) scaling phases to obtain a minimum-cost flow.

Every abundant component \(A\) of \(G\) has a representative vertex \(\boldsymbol{r_A \in A}\). Any other vertex in \(A\) is a non-representative vertex. The algorithm maintains the following two key invariants:

Invariant 6.55 (Flow Invariant): During the \(i\)th scaling phase, the flow along every non-abundant edge \(e \in G\) is a multiple of \(\Delta^{(i)}\): \(f(e) = k\Delta^{(i)}\) for some \(k \in \mathbb{N}\).

Invariant 6.56 (Excess Invariant): The excess of every non-representative vertex is \(0\).