Chapter 12 · Cuts and Flows
Cuts and Flows
The definitions, the capacity bound, and why "flow" and "cut" are the same optimisation seen from two sides.
A directed graph with source s, sink t, and capacities c(u,v) ≥ 0. A flow is f : E → ℝ≥ 0 with
- capacity: f(u,v) ≤ c(u,v),
- conservation: ∑v f(v,u) = ∑w f(u,w) for every u ∉ {s,t}.
Its value is |f| = ∑v f(s,v) - ∑v f(v,s). With antisymmetric f (the convention in code: f(u,v) = -f(v,u)), conservation becomes ∑v f(v,u) = 0 for internal u and the value is just the net out-flow of s.
An s–t cut is a partition (S, bar S) with s ∈ S, t ∈ bar S; its capacity is
— edges forward only. Backward edges do not count: they carry flow the other way, which helps, so ignoring them is the correct accounting.
For every flow f and every s–t cut (S,bar S): |f| ≤ c(S, bar S).
|f| = ∑u ∈ S, v ∉ S f(u,v) - ∑u ∉ S, v ∈ S f(u,v) — conservation makes all internal terms cancel when you sum the balance equations over S. Dropping the (non-negative) second sum and applying f ≤ c on the first gives |f| ≤ ∑u∈ S, v∉ S c(u,v). ∎
maxf |f| = min(S,bar S) c(S,bar S), and both are attained. (Proof: Max Flow: Ford–Fulkerson, Dinic, Push–Relabel — the min cut is read off the residual graph after saturation.)
The vocabulary you will need for every modelling problem
- residual capacity r(u,v) = c(u,v) - f(u,v) + f(v,u); an edge with r > 0 is a residual edge,
- an augmenting path is an s ⇝ t path of residual edges; augmenting along it by the bottleneck increases |f| by exactly that amount,
- a flow is maximum iff the residual graph has no s ⇝ t path (integrality: if all capacities are integral, the algorithm keeps f integral — this is why flow counts things),
- the min cut is S = vertices reachable from s in the final residual graph; it is the smallest such S (source side) and its complement, the vertices that can reach t, is the largest — knowing which side is which settles a whole class of "which side does vertex x belong to" questions.
Flow algorithms are only as useful as the encoding: "the min cut of a network you built" equals the answer of a combinatorial problem. The recurring encodings, with their proofs of correctness all being "a cut is exactly a valid object here":
- project selection / maximum weight closure (Min-Cut Models),
- minimum vertex cover in bipartite graphs = maximum matching (Kőnig, Kőnig's Theorem and Minimum Covers),
- "delete fewest edges/vertices so that s and t disconnect" — Menger, made algorithmic by unit capacities (Connectivity, Bridges, Articulation Points),
- binary energy minimisation with submodular pairwise terms — the graph cut of computer vision,
- Dilworth's theorem as a flow on a poset DAG (DAGs and Topological Order's chain-cover remark, made algorithmic in Bipartite Matching (Kuhn's Algorithm)).