6.9.2. Active Vertices, Low or High Excess

I mentioned that the enhanced capacity scaling algorithm may move an amount of flow from an excess vertex \(x\) to a deficit vertex \(y\) that exceeds \(e_x\) or \(-e_y\). When this happens, \(x\) turns into a deficit vertex or \(y\) turns into an excess vertex, possibly both. To ensure that the algorithm makes progress towards establishing flow conservation, at least one of \(x\) and \(y\) must be chosen to have a sufficiently high excess or deficit, that is, it must be a high-excess or high-deficit vertex according to the following definition.

A vertex \(x\) is active during the \(i\)th scaling phase if \(|e_x| > \frac{\Delta^{(i)}}{n}\).

An active vertex is a high-excess or high-deficit vertex if \(|e_x| > \bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\).

If \(\frac{\Delta^{(i)}}{n} < |e_x| \le \bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\), it is a low-excess or low-deficit vertex.

Note that only representative vertices of abundant components can be active, by the Excess Invariant.

The goal of each scaling phase of the enhanced capacity scaling algorithm is to eliminate all high-excess and all high-deficit vertices. Once it has achieved this goal, the phase ends. To make progress towards this goal, every flow augmentation chooses a high-excess vertex to send flow from or a high-deficit vertex to send flow to, possibly both. To ensure that no augmentation creates a new high-excess or high-deficit vertex, the other endpoint must be active. By the following observation, there always exists such a vertex.

Observation 6.57: If \(G^f\) has a high-excess vertex, then there exists an active deficit vertex. If \(G^f\) has a high-deficit vertex, then there exists an active excess vertex.

Proof: Consider the case when there exists a high-excess vertex \(x\). The case when there exists a high-deficit vertex is analogous.

Since \(e_x > \bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\), the total excess of all excess vertices is also greater than \(\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\). Since the total excess of all vertices is \(0\), this implies that the total deficit of all deficit vertices is also greater than \(\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\). Since \(x\) is an excess vertex, there are at most \(n - 1\) deficit vertices. Thus, there must exist a deficit vertex with deficit greater than \(\frac{1}{n - 1}\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)} = \frac{\Delta_{(i)}}{n}\). This deficit vertex is active. ▨

By the next observation, sending \(\Delta^{(i)}\) units of flow from an active excess vertex to an active deficit vertex does not create any new high-excess or high-deficit vertex. Thus, sending \(\Delta^{(i)}\) units of flow from a high-excess vertex to an active deficit vertex or from an active excess vertex to a high-deficit vertex makes progress towards eliminating all high-excess and all high-deficit vertices.

Observation 6.58: If \(x\) is an active excess vertex and \(y\) is an active deficit vertex, then after sending \(\Delta^{(i)}\) units of flow from \(x\) to \(y\), \(x\) is is not a high-deficit vertex and \(y\) is not a high-excess vertex. After the augmentation, \(x\) can be a high-excess vertex only if it was a high-excess vertex before the augmentation; \(y\) can be a high-deficit vertex only if it was a high-deficit vertex before the augmentation.

Proof: The new excess of \(x\) is \(e'_x = e_x - \Delta^{(i)} < e_x\). Thus, \(x\) can be a high-excess vertex after the augmentation only if it was a high-excess vertex before the augmentation.

Since \(e_x > \frac{\Delta^{(i)}}{n}\) because \(x\) is an active excess vertex, we have \(e'_x = e_x - \Delta^{(i)} > \frac{\Delta^{(i)}}{n} - \Delta^i = -\bigl(1 - \frac{1}{n}\bigr)\Delta^{(i)}\), so \(x\) does not become a high-deficit vertex.

The argument for \(y\) is analogous. ▨