The Edmonds-Karp O(VE) Augmentation Bound

From Residual Distances to an Augmentation Bound

Edmonds–Karp is the Ford–Fulkerson method in which each augmenting path is chosen to have the fewest residual arcs. Its number of augmentations is bounded even when capacities are not integers: the bound depends on the size of the network, not on the magnitudes of its capacities. The key is to track shortest-path distances from the source and the arcs that become bottlenecks.

Throughout, let \((G,c,s,t)\) be a finite directed network with distinct source \(s\) and sink \(t\), and finite nonnegative capacities. Write \(n=|V(G)|\) and \(m=|E(G)|\). Each original edge has a forward residual arc and a paired reverse residual arc; treat these as distinct labelled arc identities, even if two arcs have the same endpoints. Thus there are at most \(2m\) residual arc identities. For an edge \(uv\), if its current flow is \(f(uv)\), its forward residual capacity is \(c(uv)-f(uv)\), and the reverse residual capacity is \(f(uv)\). A residual arc is available when its residual capacity is positive.

All distances below are measured just before the particular augmentation under discussion. A shortest path can be taken to have no repeated vertices: if a path repeats a vertex, removing the intervening cycle produces a shorter path. Consequently, every finite distance is at most \(n-1\). Breadth-first search finds these shortest paths because every residual arc has unit length for this purpose.

Residual Distances Never Decrease

Proof. Denote old distances by \(d_{\mathrm{old}}\) and new distances by \(d_{\mathrm{new}}\). Consider any residual arc \(xy\) available after the augmentation. If it was available before, then whenever \(d_{\mathrm{old}}(x)\) is finite, the definition of shortest distance gives \(d_{\mathrm{old}}(y)\le d_{\mathrm{old}}(x)+1\). Otherwise the arc is newly available because the augmentation used its paired arc \(yx\) on the old shortest path. In that case both endpoints were reachable, and the shortest-path property gives \(d_{\mathrm{old}}(x)=d_{\mathrm{old}}(y)+1\), which also implies \(d_{\mathrm{old}}(y)\le d_{\mathrm{old}}(x)+1\).

Now take any vertex \(z\) reachable in the new residual network and a new shortest path \(s=v_0,v_1,\ldots,v_\ell=z\). Starting at \(v_0=s\), whose old distance is \(0\), apply the arc inequality at each step. Inductively, each \(v_i\) has finite old distance and \(d_{\mathrm{old}}(v_i)\le i\). Therefore \(d_{\mathrm{old}}(z)\le\ell=d_{\mathrm{new}}(z)\). This proves the claimed inequality for every newly reachable vertex. If \(z\) was unreachable before, the inequality just proved rules out its being reachable afterward. \(\square\)

The theorem compares distances across successive residual networks, not distances along one fixed path. A reverse residual arc can become available after an augmentation, but its appearance does not invalidate the distance comparison: its direction is opposite to an arc on the old shortest path.

Why a Residual Arc Cannot Be Critical Often

Suppose a labelled residual arc \(e=uv\) is critical at some augmentation. The augmentation saturates \(e\), making its residual capacity zero. For \(e\) to be critical again later, it must first become available again. Its residual capacity can increase only when an augmentation uses its paired reverse arc \(\bar e=vu\).

Proof. Let \(i\) be the earlier augmentation and \(j\) the later one. Since \(e\) is critical at \(i\), it is on that shortest path, so \(d_i(v)=d_i(u)+1\). After the augmentation, \(e\) is saturated. Before it can be critical at \(j\), an intervening augmentation must use \(\bar e=vu\) to increase \(e\)'s residual capacity. Let \(k\) denote the state just before one such augmentation. The reverse arc is on a shortest path in that state, so \(d_k(u)=d_k(v)+1\). The distance theorem gives \(d_k(v)\ge d_i(v)\), and hence \(d_k(u)\ge d_i(v)+1=d_i(u)+2\). Distances cannot decrease in the subsequent augmentations either, so \(d_j(u)\ge d_k(u)\ge d_i(u)+2\). \(\square\)

At every critical occurrence, the tail \(u\) is reachable and \(0\le d(u)\le n-1\). Each later critical occurrence of the same arc requires its tail distance to rise by at least two. Thus an arc can be critical at most \(n\) times (indeed, the distance range gives a slightly sharper bound). This count applies separately to each labelled residual arc, including reverse arcs.

The Edmonds–Karp Augmentation Bound

Proof. Each augmentation has a finite residual \(s\)-\(t\) path. Every arc on it has positive residual capacity, so the minimum of these finitely many positive capacities is positive. At least one arc attains that minimum and is therefore critical; it becomes saturated in the augmentation.

There are at most \(2m\) labelled residual arc identities. By the lemma and the finite distance range, each can be critical at most \(n\) times. Therefore the total number of critical occurrences is at most \(2mn\). Since every augmentation contributes at least one critical occurrence, the number of augmentations is at most \(2mn\). This also rules out an infinite sequence of augmentations: such a sequence would require more critical occurrences than the finite bound allows. The argument uses no integrality assumption on capacities. \(\square\)

What the Bound Does—and Does Not—Say

The capacity values determine how much flow an augmentation sends, but they do not enter the counting argument. Instead, the argument assigns each augmentation to one of its critical arcs. A given arc cannot be assigned too many times because each return to criticality forces a lasting increase in the distance to its tail. That distance is an integer between \(0\) and \(n-1\), so it has only a bounded number of possible increases.

A common mistake is to count only the \(m\) original forward edges. Augmentations can also use reverse residual arcs, as the first worked example does with \(ca\). The count must include both residual directions for every original edge, giving at most \(2m\) identities. A different mistake is to claim that each arc can be critical at most once: an arc can be restored by using its reverse and can later become critical again. The distance increase, not permanent saturation, is what bounds the number of repetitions.

This result bounds the number of augmentations only. It does not by itself count the work required to find a shortest residual path at each step; that separate accounting gives the running-time bound. The distinction matters: a bound on how many times an algorithm updates a solution and a bound on the cost of each update are different claims.