Chapter 12 · Cuts and Flows
Min-Cut Models
Seven reductions where the answer of a combinatorial problem is exactly a minimum cut — maximum closure, bipartite covering, project selection, and the submodular energy.
In a digraph, a set S is a closed set (down-set) if u ∈ S and u → v imply v ∈ S. The maximum weight closure problem: maximise ∑v ∈ S wv over closed S, with weights of both signs.
Build s → v with capacity wv for wv > 0; v → t with capacity -wv for wv < 0; every original edge u → v with capacity ∞. Then
and the optimal S is the source side of the min cut.
For any cut (A, bar A) with s ∈ A, t ∉ A, put S = A ∖ {s}. If S is not closed, some edge u → v leaves S (u in, v out), contributing ∞ — so finite cuts are exactly the closed sets. For a closed S, the cut pays: (i) each positive wv with v ∉ S (the edge s → v is cut), and (ii) each |wv| with v ∈ S (the edge v → t is cut). So
which is minimised exactly when the closure's weight is maximised. ∎
The catalogue (each is the same three lines)
- Project selection: profit pi, cost cj of prerequisites ⇒ closure with weights pi - cj. Add "∞" edges from each project to its prerequisites.
- Maximum weight independent set in a bipartite graph = total weight − min vertex cover: for each left vertex a weight, for each right a weight, edges l → r with ∞, then s→ l (weight), r→ t (weight) — the ∞ edges forbid "both endpoints kept" exactly as needed; complements turn a cover into an independent set (Kőnig's Theorem and Minimum Covers).
- Minimum vertex cover in bipartite graphs (unweighted): source → left (cap 1), matching edges left→right (∞), right → sink (cap 1); the min cut has size = max matching (Kőnig's proof is this construction).
- Minimum number of edges/vertices to delete to separate s,t (Connectivity, Bridges, Articulation Points): unit capacities on edges, or vertex-splitting vin→ vout with capacity 1 for vertices.
- Maximum density subgraph / fractional covering: parametric min cut — binary search λ, solve "is there S with ∑v∈ S(wv - λ) > 0?" as a closure, O(log) max-flow runs.
- Binary energy minimisation: variables xi ∈ {0,1}, unary terms go on s-/t-edges, a pairwise term Vij(0,1)+Vij(1,0) ≥ Vij(0,0)+Vij(1,1) (submodularity) becomes one edge of capacity frac{Vij(0,1)+Vij(1,0)-Vij(0,0)-Vij(1,1)}{2}; the min cut is the global optimum — this is the "graph cut" of vision, and it fails the instant submodularity is violated.
- Chain/antichain coverings in posets (Dilworth) — a matching problem in disguise (Bipartite Matching (Kuhn's Algorithm)).
Three signals that a min cut is hiding: (a) a choice of "keep / drop" per object with a penalty for a one-directional implication; (b) "minimum deletions to break all paths / all pairs"; (c) a bipartite structure where constraints are "not both" or "at least one of two". In each case, write the objective as ∑ (kept profits) - ∑ (penalties) and ask: which constraint becomes an ∞ edge?
Use ∞ = 1 + ∑ |w| (or 1015 with long long), never INT_MAX: a relaxation flow += min(pushed, cap) over a saturated path plus INF - x arithmetic overflows, and INT_MAX capacities in a 1000-edge graph sum to 2×1012 in the wrong type. Also: if the min cut you get has value ≥ ∞, your model is wrong — a finite cut must always exist (e.g. take all positive vertices, if that is closed).
After a max flow, "which projects are in the optimal set" = the source side of the minimum cut; "which items must be in every optimum" = vertices that reach t in the residual graph too... precisely: v is in all min cuts' source sides iff s ⇝ v in the residual graph; v is in no min cut iff v ⇝ t. To enumerate all min cuts, condense the residual graph — the min cuts are the closed sets of the condensation separating scc(s) from scc(t) (Max Flow: Ford–Fulkerson, Dinic, Push–Relabel's lattice remark).