# Ahuja-Orlin

## Contents

## General Information

**Algorithmic problem:** Max-flow problems (standard version)

**Type of algorithm:** loop

## Abstract View

**Auxiliary data:**

- A nonnegative integral value [math]d(v)[/math] for each node [math]v\in V[/math].
- Each node [math]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]v[/math]. - A stack [math]S[/math] of nodes.

**Invariant:**
After [math]i \ge 0[/math] iterations:

- The flow [math]f[/math] is a feasible flow.
- If all upper bounds are integral, [math]f[/math] is integral as well.
- The values [math]d(\cdot)[/math] are a valid distance labeling with respect to [math]f[/math].
- The current arc of a node [math]v\in V\setminus\{s,t\}[/math] is either void or one of the outgoing arcs of [math]v[/math]. No admissible outgoing arc of [math]v[/math] precedes the current arc of [math]v[/math].
- Stack [math]S[/math] contains a cycle-free flow-augmenting path with respect to [math]f[/math]. This path starts with [math]s[/math] and ends at an arbitrary node of [math]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:

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

**Break condition:** It is [math]d(s)=n[/math], where [math]n=|V|[/math],

## Induction basis

**Abstract view:**

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

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

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

## Induction step

**Abstract view:**

- Let [math]v[/math] be the top element of [math]S[/math], that is, the endnode of the corresponding path.
- If [math]v=t[/math]:
- Augment the current flow along the path corresponding to [math]S[/math] up to saturation.
- Remove all nodes but [math]s[/math] from [math]S[/math].

- Otherwise:
- While the current arc of [math]v[/math] is not void and not admissible or points to [math]s[/math]: Move the current arc one step forward.
- If the current arc of [math]v[/math] is now void:
- Set [math]d(v):=\tilde{d}+1[/math], where [math]\tilde{d}[/math] denotes the minimum value [math]d(w)[/math] over all outgoing arcs [math](v,w)[/math] of [math]v[/math] in the residual network.
- Reset the current arc of [math]v[/math] to the beginning of the list of outgoing arcs of [math]v[/math].
- Remove [math]v[/math] from [math]S[/math].

- Otherwise, that is, if the current arc is some arc [math](v,w)[/math]: Push [math]w[/math] on [math]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]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]d(v)[/math]. Finally, point 3 of the invariant follows from the conservative increase of [math]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](s,t)[/math]-path. However, such a path would have at most [math]n-1[/math] arcs, and for each arc [math](v,w)[/math] on this path, it is [math]d(v)\leq d(w)+1[/math]. This implies [math]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]\mathcal{O}(n^2m)[/math], where [math]n=|V|[/math] and [math]m=|A|[/math].

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

To see that, recall that [math]d(s)\lt n[/math] as long as the break condition is not fulfilled. Whenever the distance label [math]d(v)[/math] of a node [math]v\in V[/math] is increased, [math]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]d(v)\leq d(s)[/math] immediately before the current iteration (equality only if [math]v=s[/math]). Let [math](v,w)[/math] be an arc such that [math]\tilde{d}=d(w)[/math], in particular, it is [math]w\neq s[/math]. For the same reason, it is [math]d(w)\lt d(s)[/math], which implies [math]d(v)\leq d(s)[/math] immediately after the current iteration.

Now we know [math]d(u)\leq n[/math] for all nodes [math]u\in V[/math]. Next we consider an arbitrary but fixed arc [math](v,w)\in A[/math]. Suppose [math](v,w)[/math] has ben saturated at least twice during the algorithm. In both iterations, [math](v,w)[/math] is admissible, which means [math]d(v)\gt d(w)[/math]. However, in the meantime, some flow must have been sent back from [math]w[/math] to [math]v[/math], which implies [math]d(w)\gt d(v)[/math] in that intermediate iteration. As distance labels are non-decreasing, [math]d(v)[/math] must have been increased between any two iterations in which [math](v,w)[/math] is saturated. In summary, each arc is saturated only [math]\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]\mathcal{O}(nm)[/math]. The path contains at most [math]n-1[/math] arcs, so the total asymptotic complexity for all executions of step 2.1+2 is in [math]\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]d(v)[/math], so the total asymptotic complexity of all executions of step 3.1 over all iterations is in [math]\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](s,t)[/math]-path. This task amounts to computing the true distance from every node to [math]t[/math]. A valid distance labeling may be seen as "lazily evaluated" true distances.