Network Flows - Part 4

In Part 3, we proved the Max-Flow Min-Cut Theorem and saw that augmenting paths are the key to finding maximum flows. The natural algorithm is clear: start with the zero flow, find an augmenting path in the residual graph, push flow along it, and repeat. But several important questions remain. Does this process always terminate? How do we choose which augmenting path to use? And how fast is the resulting algorithm? In this part, we'll answer all three questions.

The Ford-Fulkerson Method

Let's start by writing down the augmenting path strategy as a precise algorithm. The Ford-Fulkerson method, introduced by Lester Ford and Delbert Fulkerson in 1956, is the framework that makes this idea concrete.

Ford-Fulkerson Method:

1. Initialize $f(a) = 0$ for every arc $a \in A$.
2. Build the residual graph $D_f$.
3. Search for an augmenting path $P$ from $s$ to $t$ in $D_f$.
4. If no augmenting path exists, stop — $f$ is a maximum flow.
5. Otherwise, compute the bottleneck $\Delta(P) = \min_{(u,v) \in P} c_f(u,v)$.
6. Update the flow: for each arc $(u,v)$ on $P$, if $(u,v)$ is a forward arc, set $f(u,v) \leftarrow f(u,v) + \Delta(P)$; if it corresponds to a backward arc $(v,u)$, set $f(v,u) \leftarrow f(v,u) - \Delta(P)$.
7. Go to step 2.

We call this a "method" rather than an "algorithm" because it doesn't specify how to find the augmenting path in step 3. Any search procedure — depth-first search, breadth-first search, or something else entirely — can be used. As we'll see, this choice has a dramatic impact on performance.

Correctness

The correctness of the Ford-Fulkerson method follows directly from the Max-Flow Min-Cut Theorem (Theorem 1 from Part 3). When the method terminates, no augmenting path exists in the residual graph. By the equivalence of conditions (i) and (ii) in the theorem, the current flow is maximum.

We should also verify that each augmentation produces a valid flow. This is straightforward: the capacity constraints are preserved because we only push $\Delta(P)$ units, which is at most the residual capacity on every arc. Flow conservation is preserved because on each intermediate vertex of the path, the incoming flow and outgoing flow both change by the same amount $\Delta(P)$.

Termination

Correctness tells us that if the method stops, it gives the right answer. But does it always stop?

For integer capacities, the answer is yes. Each augmentation increases the flow value by at least $1$ (since the bottleneck is a positive integer). The flow value is bounded above by any cut capacity, which is finite. So the method must terminate after at most $|f^*|$ augmentations, where $|f^*|$ is the maximum flow value.

Observation 2. With integer capacities, the Ford-Fulkerson method terminates after at most $|f^*|$ augmentations.

This gives a running time of $O(m \cdot |f^*|)$, since each augmentation requires finding a path in the residual graph (which takes $O(m)$ time using BFS or DFS, where $m = |A|$). For networks with small flow values, this is perfectly fine. But the flow value $|f^*|$ can be enormous — it can be exponential in the size of the network.

Consider the following example. Take a network with vertices $\{s, a, b, t\}$ and arcs $(s,a)$, $(s,b)$, $(a,b)$, $(a,t)$, $(b,t)$ with capacities $c(s,a) = c(s,b) = c(a,t) = c(b,t) = C$ and $c(a,b) = 1$, where $C$ is a large integer. The maximum flow is $2C$. A clever adversary could force the algorithm to alternately find augmenting paths $s \to a \to b \to t$ and $s \to b \to a \to t$, each pushing only $1$ unit through the bottleneck arc $(a,b)$ or its reverse. This would require $2C$ augmentations — even though a smarter choice of paths would solve the problem in just $2$ augmentations¹.

For irrational capacities, the situation is even worse: there exist examples where the Ford-Fulkerson method does not terminate at all. The flow values can converge to a limit that is not the maximum flow. This was shown by Uri Zwick in 1993 and is one of the reasons why the Ford-Fulkerson method is considered a framework rather than a complete algorithm — it needs a good path-selection rule to guarantee termination and efficiency.

The Edmonds-Karp Algorithm

The weakness of the Ford-Fulkerson method is its freedom in choosing augmenting paths. Jack Edmonds and Richard Karp (and independently Yefim Dinitz) discovered in 1972 that a simple rule eliminates all the problems: always choose a shortest augmenting path, where "shortest" means fewest arcs.

Definition 10. The Edmonds-Karp algorithm is the Ford-Fulkerson method where the augmenting path in each iteration is a shortest $s$-$t$-path in the residual graph $D_f$, found using breadth-first search (BFS).

BFS explores vertices layer by layer: first all vertices at distance $1$ from $s$, then distance $2$, and so on. It naturally finds a shortest path in $O(m)$ time. By always augmenting along a shortest path, we ensure that the residual graph doesn't develop "shortcuts" that could lead to the pathological behavior we saw above.

Analysis

The key to analyzing the Edmonds-Karp algorithm is the following lemma, which shows that distances in the residual graph can only increase over time.

For a flow $f$, let $d_f(v)$ denote the shortest-path distance (in number of arcs) from $s$ to $v$ in the residual graph $D_f$.

Lemma 2. Let $f$ be a flow, and let $f'$ be the flow obtained after one augmentation along a shortest path. Then $d_{f'}(v) \geq d_f(v)$ for every vertex $v \in V$.

The proof uses a careful argument by contradiction: if some vertex got closer to $s$ after the augmentation, we can trace back the new shorter path and show that it must use an arc that was created by the augmentation — but this leads to a contradiction with the fact that we augmented along a shortest path. We omit the full proof here, but the intuition is that augmenting along shortest paths is "conservative" — it doesn't create shortcuts in the residual graph.

With this lemma, we can bound the total number of augmentations.

Theorem 3. The Edmonds-Karp algorithm performs at most $O(nm)$ augmentations, where $n = |V|$ and $m = |A|$.

Proof sketch. We call an arc $(u,v)$ on an augmenting path critical if it has the minimum residual capacity — that is, $c_f(u,v) = \Delta(P)$. After augmenting, a critical arc disappears from the residual graph (its residual capacity drops to zero).

Consider a specific arc $(u,v)$. When it is critical, we have $d_f(v) = d_f(u) + 1$ (since it lies on a shortest path). For $(u,v)$ to reappear in the residual graph later, flow must be pushed backwards through it — meaning $(v,u)$ must appear on some future augmenting path. At that point, $d_{f''}(u) = d_{f''}(v) + 1$. By Lemma 2, distances never decrease, so: $d_{f''}(u) = d_{f''}(v) + 1 \geq d_f(v) + 1 = d_f(u) + 2.$

Each time an arc becomes critical, the distance of one of its endpoints from $s$ increases by at least $2$. Since distances are bounded by $n$ (there are only $n$ vertices), each arc can be critical at most $O(n)$ times. There are $O(m)$ arcs, so the total number of critical arc events is $O(nm)$. Since each augmentation has at least one critical arc, the total number of augmentations is at most $O(nm)$.

Since each augmentation takes $O(m)$ time (for BFS plus the flow update), the total running time is:

Corollary 2. The Edmonds-Karp algorithm runs in $O(nm^2)$ time.

This is a polynomial bound that depends only on the size of the network, not on the magnitude of the capacities. Whether the capacities are $1$ or $1{,}000{,}000$, the algorithm runs in the same polynomial time.

A Worked Example

Let's trace the Edmonds-Karp algorithm on a slightly larger network to see it in action. Consider the network with vertices $\{s, a, b, c, t\}$ and the following arcs and capacities:

$c(s,a) = 10, \quad c(s,b) = 8, \quad c(a,b) = 5, \quad c(a,c) = 7, \quad c(b,c) = 10, \quad c(b,t) = 7, \quad c(c,t) = 10.$

Iteration 1. Starting from the zero flow, the residual graph equals the original network. BFS from $s$ finds a shortest path. One such path is $s \to a \to c \to t$ with bottleneck $\min(10, 7, 10) = 7$. We push $7$ units: $f(s,a) = 7$, $f(a,c) = 7$, $f(c,t) = 7$. Flow value: $7$.

Iteration 2. BFS finds $s \to b \to t$ with bottleneck $\min(8, 7) = 7$. We push $7$ units: $f(s,b) = 7$, $f(b,t) = 7$. Flow value: $14$.

Iteration 3. BFS finds $s \to a \to b \to c \to t$ with bottleneck $\min(3, 5, 10, 3) = 3$. We push $3$ units: $f(s,a) = 10$, $f(a,b) = 3$, $f(b,c) = 3$, $f(c,t) = 10$. Flow value: $17$.

Iteration 4. BFS finds $s \to b \to c \to t$. The residual capacities are $c_f(s,b) = 1$, $c_f(b,c) = 7$, $c_f(c,t) = 0$ — but $c_f(c,t) = 0$, so this path is blocked. In fact, no path from $s$ to $t$ exists in the residual graph: the arcs $(c,t)$ and $(a,c)$ are fully saturated, and the remaining forward capacity out of $s$ is only $c_f(s,b) = 1$, but it cannot reach $t$².

Wait — let's be more careful. Let me recheck. From $s$: we can reach $b$ (residual $1$ on $(s,b)$) and $a$ via $(a,s)$? No, $(a,s)$ is a backward arc with residual $10$, but that goes from $a$ to $s$ — it doesn't help us leave $s$. Actually, $s$ can go to $b$ with residual $1$. From $b$: $(b,t)$ has residual $0$, $(b,c)$ has residual $7$, and there's a backward arc $(b,a)$ with residual $3$. From $c$: $(c,t)$ has residual $0$, backward arcs $(c,a)$ with residual $7$ and $(c,b)$ with residual $3$. None of these reach $t$.

So the algorithm terminates with maximum flow $|f^*| = 17$. The minimum cut can be read from the residual graph: $S$ is the set of vertices reachable from $s$, which is $\{s, b, c, a\} = \{s, a, b, c\}$ and $T = \{t\}$. The cut capacity is $c(b,t) + c(c,t) = 7 + 10 = 17$, confirming $|f^*| = 17$.

The algorithm needed only $3$ augmentations — far fewer than the theoretical bound of $O(nm)$ — because BFS guided us to efficient choices.

Looking Ahead

The Edmonds-Karp algorithm gives us a reliable polynomial-time method for computing maximum flows. While $O(nm^2)$ is efficient enough for many practical purposes, faster algorithms exist — Dinitz's algorithm achieves $O(n^2 m)$ using the concept of blocking flows, and more recent algorithms improve this further.

In the next part, we'll shift from algorithms to applications. We'll see how maximum flow can be used to solve problems that, at first glance, have nothing to do with flows: bipartite matching, edge-disjoint paths, and project selection. These applications demonstrate the remarkable versatility of network flow theory.