Preflow-push with excess scaling

Abstract view

Algorithmic problem: max-flow problem (standard version)

This is a specialization of the generic preflow-push algorithm:

1. An additional nonnegative integral number [math]\displaystyle{ \Delta }[/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, cf. here).
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 do not apply a push or relabel operation but reset [math]\displaystyle{ \Delta:=\Delta/2 }[/math] (integral division) repeatedly until there is an active node with large excess or [math]\displaystyle{ \Delta=0 }[/math].

Invariant:

1. All invariants of the generic pre-flow push algorithm.
2. 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].

Variant: The variant of the generic pre-flow push algorithm is extended by a fourth option: The value of [math]\displaystyle{ \Delta }[/math] is reduced to [math]\displaystyle{ \Delta/2 }[/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 of the abstract algorithm

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] with large excess and [math]\displaystyle{ d(v)=k }[/math]. This array is computed from scratch in the initialization and after every reduction 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 is never decreased by more than one unit at a time.

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 forward steps of current arcs, and [math]\displaystyle{ \mathcal{O}(n\!\cdot\!m) }[/math] saturating push steps. Due to the above implementation of point 3, all node selections have complexity [math]\displaystyle{ \mathcal{O}(P+n\cdot\log U) }[/math] in total, where [math]\displaystyle{ P }[/math] is the total number of saturating and non-saturating push steps.

So, 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, dynamically changing potential function:

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

The parameters of [math]\displaystyle{ \Phi }[/math] are evident, so they are omitted for convenience. Since [math]\displaystyle{ e_f(v)\leq\Delta }[/math], it is [math]\displaystyle{ \Phi\leq\sum_{v\in V\setminus\{s,t\} }[/math], so 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]. Consequently, the number of non-saturating push steps is in [math]\displaystyle{ \mathcal{O}(n^2) }[/math] in each scaling phase.

Remark: Potential functions are a general concept for complexity considerations. The sum and the maximum of all [math]\displaystyle{ d }[/math]-labels are rather simple examples of potential functions, which are used for the complexity considerations for the generic pre flow-push algorithm and for the FIFO variant, respectively.