Ahuja-Orlin

General Information

Algorithmic problem: Max-flow problems (standard version)

Type of algorithm: loop

Abstract View

Auxiliary data:

1. A nonnegative integral value [math]\displaystyle{ d(v) }[/math] for each node [math]\displaystyle{ v\in V }[/math].
2. Each node [math]\displaystyle{ v\in V\setminus\{t\} }[/math] has a current arc, which may be implemented as an iterator on the list of outgoing arcs of [math]\displaystyle{ v }[/math].
3. A stack [math]\displaystyle{ S }[/math] of nodes.

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

1. The flow [math]\displaystyle{ f }[/math] is a feasible flow.
2. If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.
3. The values [math]\displaystyle{ d(\cdot) }[/math] are a valid distance labeling with respect to [math]\displaystyle{ f }[/math].
4. The current arc of a node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math] is either void or one of the outgoing arcs of [math]\displaystyle{ v }[/math]. No admissible outgoing arc of [math]\displaystyle{ v }[/math] precedes the current arc of [math]\displaystyle{ v }[/math].
5. Stack [math]\displaystyle{ S }[/math] contains a cycle-free flow-augmenting path with respect to [math]\displaystyle{ f }[/math]. This path starts with [math]\displaystyle{ s }[/math] and ends at an arbitrary node of [math]\displaystyle{ G }[/math]. Each arc on this path is admissible and the current arc of its tail node.

Variant: One of the following actions will take place in the current iteration:

1. An arc is appended to the current path (when going forward in the depth-first search for an augmenting path).
2. At least one arc is saturated (when augmenting along the path up to saturation).
3. The distance label of some node is increased (when going forward in the depth-first search for an augmenting path).

Break condition: It is [math]\displaystyle{ d(s)\geq n }[/math], where [math]\displaystyle{ n=|V| }[/math],

Induction basis

Abstract view:

1. We start with some feasible flow, for example, the zero flow.
2. Also, we start with some valid distance labeling with respect to the initial flow.
3. Stack [math]\displaystyle{ S }[/math] is initialized so as to contain [math]\displaystyle{ s }[/math] and no other node.
4. The current arc of each node [math]\displaystyle{ v\in V }[/math] is reset to be the very first outgoing arc of [math]\displaystyle{ v }[/math].

Implementation of step 2 in case [math]\displaystyle{ f }[/math] is initialized as the zero flow: A BFS is run on the transpose of [math]\displaystyle{ G }[/math] with start node [math]\displaystyle{ t }[/math]; the resulting distances are the [math]\displaystyle{ d }[/math]-labels.

Proof of the implementation: Clearly, it is [math]\displaystyle{ d(t)=0 }[/math], so it remains to show [math]\displaystyle{ d(v)\leq d(w)+1 }[/math] for each arc [math]\displaystyle{ a\in A }[/math]. If [math]\displaystyle{ f }[/math] is the zero flow, the arcs of the residual network [math]\displaystyle{ G_f }[/math] are exactly the arcs of [math]\displaystyle{ G }[/math]. So, the claim follows immediately from the valid distance property.

Induction step

Abstract view:

1. Let [math]\displaystyle{ v }[/math] be the top element of [math]\displaystyle{ S }[/math], that is, the endnode of the corresponding path.
2. If [math]\displaystyle{ v=t }[/math]:
   1. Augment the current flow along the path corresponding to [math]\displaystyle{ S }[/math] up to saturation.
   2. Remove all nodes but [math]\displaystyle{ s }[/math] from [math]\displaystyle{ S }[/math].
3. Otherwise:
   1. While the current arc of [math]\displaystyle{ v }[/math] is not void and not admissible or points to [math]\displaystyle{ s }[/math]: Move the current arc one step forward.
   2. If the current arc of [math]\displaystyle{ v }[/math] is now void:
      1. Set [math]\displaystyle{ d(v):=\tilde{d}+1 }[/math], where [math]\displaystyle{ \tilde{d} }[/math] denotes the minimum value [math]\displaystyle{ d(w) }[/math] over all outgoing arcs [math]\displaystyle{ (v,w) }[/math] of [math]\displaystyle{ v }[/math] in the residual network.
      2. Reset the current arc of [math]\displaystyle{ v }[/math] to the beginning of the list of outgoing arcs of [math]\displaystyle{ v }[/math].
      3. Remove [math]\displaystyle{ v }[/math] from [math]\displaystyle{ S }[/math].
   3. Otherwise, that is, if the current arc is some arc [math]\displaystyle{ (v,w) }[/math]: Push [math]\displaystyle{ w }[/math] on [math]\displaystyle{ S }[/math].

Proof: The variant, points 1, 2, and 5 of the invariant, and the first sentence of point 4 of the invariant are obvious. For the second sentence of point 4, note that no admissible arc of [math]\displaystyle{ v }[/math] is skipped when the current arc is moved forward, and the current arc is reset whenever outgoing arcs may become admissible due to an increase of [math]\displaystyle{ d(v) }[/math]. Finally, point 3 of the invariant follows from the conservative increase of [math]\displaystyle{ d(v) }[/math] in step 3.2.

Correctness

First we show that the flow is maximum when the break condition applies. Due to the max-flow min-cut theorem, it suffices to show that, in this moment, there is no more flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path. However, such a path would have at most [math]\displaystyle{ n-1 }[/math] arcs, and for each arc [math]\displaystyle{ (v,w) }[/math] on this path, it is [math]\displaystyle{ d(v)\leq d(w)+1 }[/math]. This implies [math]\displaystyle{ d(s)-d(t)=d(s)\leq n-1 }[/math], which contradicts the break condition.

It remains to show that the algorithm indeed terminates. This is proved by the following complexity considerations.

Complexity

Statement: The asymptotic complexity of the algorithm is in [math]\displaystyle{ \mathcal{O}(n^2m) }[/math], where [math]\displaystyle{ n=|V| }[/math] and [math]\displaystyle{ m=|A| }[/math].

Proof: First we show that no distance label [math]\displaystyle{ d(v) }[/math] may become higher than [math]\displaystyle{ n }[/math] (in particular, the total number of executions of step 3.2 over all iterations is in [math]\displaystyle{ \mathcal{O}(n^2) }[/math]).

To see that, recall that [math]\displaystyle{ d(s)\lt n }[/math] as long as the break condition is not fulfilled. Whenever the distance label [math]\displaystyle{ d(v) }[/math] of a node [math]\displaystyle{ v\in V }[/math] is increased, [math]\displaystyle{ v }[/math] is the endnode of the current path, which consists solely of admissible arcs. Due to the definition of admissible arcs, it is [math]\displaystyle{ d(v)\leq d(s) }[/math] immediately before the current iteration (equality only if [math]\displaystyle{ v=s }[/math]). Let [math]\displaystyle{ (v,w) }[/math] be an arc such that [math]\displaystyle{ \tilde{d}=d(w) }[/math], in particular, it is [math]\displaystyle{ w\neq s }[/math]. For the same reason, it is [math]\displaystyle{ d(w)\lt d(s) }[/math], which implies [math]\displaystyle{ d(v)\leq d(s) }[/math] immediately after the current iteration.

Now we know [math]\displaystyle{ d(u)\leq n }[/math] for all nodes [math]\displaystyle{ u\in V }[/math]. Next we consider an arbitrary but fixed arc [math]\displaystyle{ (v,w)\in A }[/math]. Suppose [math]\displaystyle{ (v,w) }[/math] has ben saturated at least twice during the algorithm. In both iterations, [math]\displaystyle{ (v,w) }[/math] is admissible, which means [math]\displaystyle{ d(v)\gt d(w) }[/math]. However, in the meantime, some flow must have been sent back from [math]\displaystyle{ w }[/math] to [math]\displaystyle{ v }[/math], which implies [math]\displaystyle{ d(w)\gt d(v) }[/math] in that intermediate iteration. As distance labels are non-decreasing, [math]\displaystyle{ d(v) }[/math] must have been increased between any two iterations in which [math]\displaystyle{ (v,w) }[/math] is saturated. In summary, each arc is saturated only [math]\displaystyle{ \mathcal{O}(n) }[/math] times.

In each execution of step 2.1 of the induction step, at least one arc is saturated, so the total number of executions of step 2.1+2.2 is in [math]\displaystyle{ \mathcal{O}(nm) }[/math]. The path contains at most [math]\displaystyle{ n-1 }[/math] arcs, so the total asymptotic complexity for all executions of step 2.1+2 is in [math]\displaystyle{ \mathcal{O}(n^2m) }[/math].

Finally, the sequence of outgoing arcs is passed once for each node in step 3.1 between two increases of [math]\displaystyle{ d(v) }[/math], so the total asymptotic complexity of all executions of step 3.1 over all iterations is in [math]\displaystyle{ \mathcal{O}(n\cdot m) }[/math].

Remark

This algorithm may be seen as a "lazy" variant on Edmonds-Karp. In fact, the most expensive step there is the computation of a shortest flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path. This task amounts to computing the true distance from every node to [math]\displaystyle{ t }[/math]. A valid distance labeling may be seen as "lazily evaluated" true distances.