How much can you push from source to sink through a network of capacities — and the theorem that says the answer equals the cheapest way to cut the network in half.
A flow network is a directed graph whose edges have capacities, with a designated source and sink. The maximum-flow problem asks for the greatest rate at which material can move from source to sink without exceeding any capacity. The chapter’s centre is the max-flow min-cut theorem, one of the most useful results in combinatorial optimisation, and the Ford-Fulkerson method, whose correctness rests on the clever idea of a residual network that permits flow to be pushed backwards.
G = (V, E) is a directed graph where each edge (u,v) has a non-negative capacity c(u,v) ≥ 0. There are two distinguished vertices: the source s and the sink t. If (u,v) ∉ E then c(u,v) = 0. CLRS assumes no antiparallel edges and that every vertex lies on some path from s to t.A flow is a function f : V × V → ℝ satisfying two properties:
| Property | Statement | Meaning |
|---|---|---|
| Capacity constraint | 0 ≤ f(u,v) ≤ c(u,v) for all u,v | No edge carries more than it can hold |
| Flow conservation | For all u ∈ V - {s,t}: ∑ᵛ f(v,u) = ∑ᵛ f(u,v) | What goes in comes out; nothing accumulates |
The value of the flow is the net amount leaving the source:
|f| = ∑v∈V f(s,v) - ∑v∈V f(v,s)(u,v) and (v,u) present) are eliminated by splitting one of them through a new intermediate vertex. Multiple sources or sinks are handled by adding a supersource with infinite-capacity edges to all real sources, and symmetrically a supersink. Both reductions cost O(V + E) and mean the theory only ever has to handle the single-source single-sink case.The central construction. Given a flow f, the residual network records how much more can be pushed along each edge — including the ability to undo flow already sent.
╱ c(u,v) - f(u,v) if (u,v) ∈ E // unused capacity
cᵡ(u,v) = │ f(v,u) if (v,u) ∈ E // flow we could cancel
╱ 0 otherwiseu to v, the residual network contains an edge from v to u of capacity 5. Pushing flow along it does not move material backwards — it cancels flow that was previously routed forwards, freeing it to take a better route. Without this, a greedy algorithm can commit to a bad early routing and get stuck at a non-maximum flow.s to t in the residual network Gᵡ. Its residual capacity is the minimum residual capacity of any edge on it — the bottleneck. Augmenting by that amount yields a new, strictly larger flow.Formally, if f is a flow in G and f′ is a flow in Gᵡ, then f ↑ f′ is a flow in G with value |f| + |f′| (Lemma 24.1). Pushing along an augmenting path is the special case.
CLRS calls it a method, not an algorithm, because it does not specify how to find the augmenting path — and that choice determines the running time.
FORD-FULKERSON-METHOD(G, s, t)
1 initialize flow f to 0
2 while there exists an augmenting path p in the residual network Gᵡ
3 augment flow f along p
4 return fO(E · |f*|), which depends on the capacity values, not just the graph size — and with irrational capacities it may not terminate at all.(S, T) of a flow network partitions V into S and T = V - S with s ∈ S and t ∈ T. The net flow across the cut is f(S,T), and the capacity of the cut is c(S,T) = ∑u∈S ∑v∈T c(u,v) — note that capacity counts only forward edges, while net flow subtracts the backward ones.Two facts:
|f|. All the material has to cross somewhere.f is a flow in a flow network G with source s and sink t, then the following three conditions are equivalent:
f is a maximum flow in G.Gᵡ contains no augmenting paths.|f| = c(S,T) for some cut (S,T) of G.The proof cycles 1 ⇒ 2 ⇒ 3 ⇒ 1. The interesting step is 2 ⇒ 3: if no augmenting path exists, let S be the set of vertices reachable from s in Gᵡ. Then t ∉ S, every forward edge from S to T must be saturated (or it would still be in Gᵡ), and every backward edge from T to S must carry zero flow. Hence |f| = c(S,T).
The theorem also gives correctness of Ford-Fulkerson for free: it terminates only when there are no augmenting paths, and condition 2 implies condition 1.
That single change removes the dependence on capacity values.
Running time: O(V E²) // independent of capacitiesThe proof has two parts. First, the shortest-path distance δᵡ(s,v) in the residual network never decreases as augmentations proceed (Lemma 24.7). Second, each edge can become critical — be the bottleneck on the chosen path — at most |V|/2 times, because between two critical occurrences of the same edge its endpoints must move at least 2 further apart. With O(E) edges and O(V) criticalities each, there are O(VE) augmentations, and each BFS costs O(E).
| Algorithm | Path choice | Time |
|---|---|---|
| Ford-Fulkerson (generic) | Any | O(E · |f*|) — depends on capacity values |
| Edmonds-Karp | BFS, shortest path | O(V E²) |
| Dinic’s algorithm | Blocking flows by level graph | O(V² E) |
| Push-relabel | No paths; local pushes | O(V² E), or O(V³) with relabel-to-front |
Max-flow is a reduction target — a surprising number of problems become easy once phrased as a flow.
| Problem | Reduction |
|---|---|
| Bipartite matching | Source to all left vertices, right vertices to sink, all capacities 1. Max flow = maximum matching. This is Chapter 25. |
| Edge-disjoint paths | Set every capacity to 1; max flow = the number of edge-disjoint s-t paths (Menger’s theorem). |
| Vertex connectivity | Split each vertex into in/out halves joined by a capacity-1 edge. |
| Image segmentation | Min cut separates foreground from background pixels. |
| Project selection | Max profit becomes a min cut on a network of prerequisites. |
| Baseball elimination | Whether a team can still win reduces to a max-flow feasibility question. |
f(u,v) is an integer. This is what makes the combinatorial reductions above work — a matching cannot use half an edge, and the theorem guarantees it never has to.Gᵡ and pushes the bottleneck amount. It is a method; the path rule is left open.O(E · |f*|), which depends on the capacity values and can be catastrophic on a badly shaped network.s from t. Net flow across any cut equals |f|, and every cut upper-bounds every flow.O(VE²) independent of capacities. Each edge is critical at most |V|/2 times.Chapter 25 takes the most important of those reductions and develops it properly: matchings in bipartite graphs, including the Hopcroft-Karp speedup, the stable-marriage problem, and the Hungarian algorithm for the weighted assignment problem.