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 }[/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 do not apply a regular iteration but reset [math]\displaystyle{ \Delta:=\Delta/2 }[/math] (integral division) until there is an active node with large excess.

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

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.

Next we 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]. Consequently, the number of non-saturating push steps is in [math]\displaystyle{ \mathcal{O}(n^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 are a general concept for complexity considerations. The sum and the maximum of all [math]\displaystyle{ d }[/math]-labels are simpler potential functions, which are used for the complexity considerations for the generic pre flow-push algorithm and for the FIFO variant, respectively.