Preflow-push with excess scaling

Abstract view

Algorithmic problem: max-flow problem (standard version)

Type of algorithm: a specialiiation of the generic preflow-push algorithm:

1. An additional nonnegative integral number [math]\displaystyle{ \Delta/2 }[/math] is maintained, which is initialized to be the at least as large as the largest upper bound of any arc (but not more than the next higher power of 2 for complexity reasons).
2. In each iteration, an active node [math]\displaystyle{ v }[/math] may only be chosen if kit has large excess, that is, [math]\displaystyle{ e_f(v)\geq\Delta/2 }[/math].
3. If there are active nodes but none with large excess, we reset [math]\displaystyle{ \Delta:=\Delta/2 }[/math] (integral division) until there is an active node with large excess.

Remarks:

1. A sequence of iterations between two successive changes of [math]\displaystyle{ \Delta }[/math] is usually called a scaling phase.
2. It is quite common in the literature to define an outer loop in which each iteration performs one scaling phase, and an inner loop performs the push-relabel steps. The break condition is usually [math]\displaystyle{ \Delta=0 }[/math]. Clearly, when this condition is fulfilled, the break condition of the generic preflow-push algorithm is fulfilled as well.

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: A the generic 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.

Definition: The iterations of the following 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}(n\!\cdot\!m+n^2\!\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.