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 fleasible 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 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.
2. At least one arc is saturated.
3. The distance label of some node is increased.

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.
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] and unit arc lengths; the resulting distances are the [math]\displaystyle{ d }[/math]-labels.

Proof: 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].
   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. 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 4 of the invariant, and the first sentence of point 5 of the invariant are obvious. For point 5, note that step 2.3.1 skips all non-admissible arcs, so step 2.3.3 is only applied to admissible arcs. 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 bound.

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 [math]\displaystyle{ d(s)\lt n }[/math] from the break condition. 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]. 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+2.2, 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, so the total asymptotic complexity of all exections of step 3.1 over all iterations is linear in the number of arcs.

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.