Preflow-push with excess scaling

Abstract view

Algorithmic problem: max-flow problem (standard version)

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

1. An additional nonnegative integral number [math]\displaystyle{ \Delta/2 }[/math] is maintained, which is initialized so as to be 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.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n\!\cdot\!m+n^2\!\cdot\!\log U) }[/math], where [math]\displaystyle{ n=|V| }[/math], [math]\displaystyle{ m=|A| }[/math], and [math]\displaystyle{ U=\max\{u(a)|a\in A\} }[/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.