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 it has large excess, that is, [math]\displaystyle{ e_f(v)\geq\Delta/2 }[/math].
3. Among all active nodes with large excess, we choose one with minimum [math]\displaystyle{ d }[/math]-label.
4. 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.

Implementation of point 3: All active nodes with large excess are stored in an array of sets of nodes. The list at index [math]\displaystyle{ k }[/math] contains all active nodes [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math] such that [math]\displaystyle{ d(v)=k }[/math]. This array is computed from scratch in the initialization and after every change of [math]\displaystyle{ \Delta }[/math]. A current array index is maintained, which is not larger than the index of any non-empty node set in the array. Whenever a node is to be chosen, the current array index is increased as long as the list at the current array index is empty. A push step may result in a new active node with large excess. However, this node has to be inserted at the index immediately before the current array index, so the current array index must simply be decreased by one.

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]. Due to the above implementation of point 3, all node selections have complexity [math]\displaystyle{ \mathcal{O}(P+n\cdot\log U }[/math], where [math]\displaystyle{ P }[/math] is the total number of push steps. In summary, the claim follows.

Remark: potential functions