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.

Note: At any time, it is [math]\displaystyle{ e_f(v)\leq\Delta }[/math] for every node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math].

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: The complexity considerations for the generic preflow-push algorithm yield [math]\displaystyle{ \mathcal{O}(n^2) }[/math] relabel steps and [math]\displaystyle{ \mathcal{O}(n\!\cdot\!m) }[/math] saturating push steps and forward steps of the current arcs of all nodes in total. Hence, it suffices to show that there are [math]\displaystyle{ \mathcal{O}(n^2) }[/math] non-saturating push steps in each scaling phase. To see that, we consider the following potential function:

[math]\displaystyle{ \Phi:=\sum_{v\in V\setminus\{s,t\}}e(v)\cdot d(v)/\Delta }[/math].

Since [math]\displaystyle{ e_f(v)\leq\Delta }[/math], all relabel steps together cannot increase [math]\displaystyle{ \Phi }[/math] by more than [math]\displaystyle{ 2n^2 }[/math] (cf. here). Each push step - saturating or not - decreases this value because excess is always sent from a node with a higher [math]\displaystyle{ d }[/math]-label to a node with a (one unit) lower [math]\displaystyle{ d }[/math]-label. Therefore, we may safely ignore saturating push steps. Now, a non-saturating push sends at least [math]\displaystyle{ \Delta/2 }[/math] units of excess, which decreases [math]\displaystyle{ \Phi }[/math] by [math]\displaystyle{ 1/2 }[/math]. In summary,

Remark: potential functions