Preflow-push with excess scaling

Abstract view

Algorithmic problem: max-flow problem (standard version)

Type of algorithm: a variation of the generic preflow-push algorithm.

Invariant: Before and after each iteration:

1. All points of the invariant of the preflow-push algorithm.
2. There is a nonnegative, integral value [math]\displaystyle{ \Delta }[/math], and the excess [math]\displaystyle{ e_f(v) }[/math] of no active node [math]\displaystyle{ v }[/math] exceeds [math]\displaystyle{ \Delta }[/math].

Variant: [math]\displaystyle{ \Delta }[/math] is divided by two (integral division).

Break condition: [math]\displaystyle{ \Delta=0 }[/math].

Induction basis

1. All steps in the induction basis of the preflow push algorithm.
2. Set [math]\displaystyle{ \Delta:=2^L }[/math], where [math]\displaystyle{ L:=\lceil\log_2U\rceil }[/math] and [math]\displaystyle{ U:=\max\{u(a)|a\in A\} }[/math].

Induction step

Abstract view: Run the preflow-push algorithm with the following modifications:

1. Ignore all active nodes whose excess is smaller than [math]\displaystyle{ \Delta/2 }[/math]. In particular, an iteration of the main loop is finished once no node has an excess of [math]\displaystyle{ \Delta/2 }[/math] or more.
2. Among the nodes with excess at least [math]\displaystyle{ \Delta/2 }[/math], choose one with minimum [math]\displaystyle{ d }[/math]-label.
3. Do not push more than [math]\displaystyle{ \Delta-e_f(w) }[/math] units of flow over an arc [math]\displaystyle{ (v,w) }[/math].
4. At the end, set [math]\displaystyle{ \Delta:=\Delta/2 }[/math].

Proof: obvious.

Remark: The iterations of the main loop are usually called the scaling phases.

Correctness

Whenever an iteration is finished, no excess of [math]\displaystyle{ \Delta/2 }[/math] or more is left at any node. When the break condition applies, no excess is left at all. Termination of the main loop follows from the following complexity considerations.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(\!\cdot\!\log U) }[/math]

Proof: In an operation of the main loop, let a large excess be at least [math]\displaystyle{ \Delta/2 }[/math] and a small excess be strictly less than [math]\displaystyle{ \Delta/2 }[/math].

Due to the selection rule for the next active node, every push step moves flow from a node with large excess to a node with small excess.

...

Now it suffices to show that there are [math]\displaystyle{ \mathcal{O}(n^2) }[/math] non-saturating push steps in every scaling phase.