Maximum flow (concept + Ford-Fulkerson)

◈ 5 cards

Flow networks, residual graphs, augmenting paths, the max-flow min-cut theorem, and Edmonds-Karp (BFS augmenting paths, O(VE²)).

Flow networks

A flow network is a directed graph where each edge $(u, v)$ has a nonnegative capacity $c (u, v) \geq 0$ , with a designated source $s$ and sink $t$ . A flow $f$ assigns a value to each edge subject to two rules:

Capacity constraint: $0 \leq f (u, v) \leq c (u, v)$ — you cannot send more than an edge can carry.
Flow conservation: at every vertex except $s$ and $t$ , flow in equals flow out — nothing accumulates or appears.

The value $∣ f ∣ = \sum_{v} f (s, v) - \sum_{v} f (v, s)$ is the net flow leaving the source. The maximum-flow problem asks for the flow of greatest value.

Residual networks and augmenting paths

The key device is the residual network $G_{f}$ , which records how the flow can still change. For each edge it provides two residual capacities:

Forward residual $c_{f} (u, v) = c (u, v) - f (u, v)$ — unused capacity you can still push.
Backward residual $c_{f} (v, u) = f (u, v)$ — the ability to cancel existing flow and reroute it.

An edge appears in $G_{f}$ exactly when its residual capacity is positive. An augmenting path $p$ is any simple $s ⇝ t$ path in $G_{f}$ ; its residual capacity is the bottleneck $c_{f} (p) = min {c_{f} (u, v) : (u, v) \in p}$ . Augmenting along $p$ pushes $c_{f} (p)$ units — raising forward edges and lowering the cancelled ones — increasing $∣ f ∣$ by $c_{f} (p) > 0$ . The backward edges are what let a greedy method undo a bad earlier routing choice.

The max-flow min-cut theorem (Theorem 24.6)

A cut $(S, T)$ partitions the vertices with $s \in S$ , $t \in T$ ; its capacity $c (S, T)$ is the total capacity of edges crossing $S \to T$ . The theorem states three equivalent conditions:

$f$ is a maximum flow.
$G_{f}$ contains no augmenting path.
$∣ f ∣ = c (S, T)$ for some cut $(S, T)$ .

So max flow = min cut. The $(2) \Rightarrow (3)$ proof is constructive: when no augmenting path exists, take $S = {$ vertices reachable from $s$ in $G_{f}}$ . Then every $S \to T$ edge is saturated ( $c_{f} = 0 \Rightarrow f = c$ ) and every $T \to S$ edge carries zero flow, so the net flow across the cut equals its capacity, $∣ f ∣ = c (S, T)$ — proving maximality and exhibiting a minimum cut at once.

Ford-Fulkerson and Edmonds-Karp

Ford-Fulkerson is the method: start with $f = 0$ , and while an augmenting path exists in $G_{f}$ , augment along it. With integer capacities each augmentation adds at least $1$ , so it terminates — but choosing the path carelessly costs $O (E ∣ f^{*} ∣)$ , which is not polynomial in the input size (a $1, 000, 000$ -capacity graph can need $2, 000, 000$ augmentations).

Edmonds-Karp fixes this by always taking the shortest (fewest-edge) augmenting path via BFS. Then BFS distances from $s$ in $G_{f}$ increase monotonically, so each edge becomes a critical (bottleneck) edge at most $∣ V ∣/2$ times — yielding $O (V E)$ augmentations and a total of $O (V E^{2})$ , polynomial regardless of capacity values. By the integrality theorem, integer capacities yield an integer maximum flow — which is why bipartite matching reduces to max flow: give every edge capacity $1$ and each vertex is matched at most once.

Worked example

On the CLRS Fig 24.1 network (6 vertices $s, v_{1}, v_{2}, v_{3}, v_{4}, t = 0 \dots 5$ ) Edmonds-Karp finds a maximum flow of value 23.

The exercise network (s, v1, v2, v3, v4, t = 0–5), every edge labelled flow/capacity, after Edmonds-Karp augments along its first BFS path s→v1→v3→t. The bottleneck is min(16, 12, 20) = 12, so 12 units ride that path and every other edge still carries 0. Conservation already holds at v1…v4.

The residual network G_f of the flow above. A solid arc is leftover capacity c(u,v) − f(u,v); a dashed arc is the cancelling arc of capacity f(u,v) that lets a later path undo this routing. v1→v3 is saturated, so it disappears forwards and reappears as v3→v1 = 12. BFS still reaches t, so the flow is not yet maximum — the next shortest path is s→v2→v4→t with bottleneck 4.

At the maximum flow, S = {s, v1, v2, v4} is exactly the set still reachable from s in the residual network and T = {v3, t} is the rest. Every edge leaving S is saturated — 12/12, 7/7, 4/4 — and the one edge coming back, v3→v2, carries 0. So |f| = c(S,T) = 23: max flow equals min cut, and the cut is read straight off the residual network.