Minimum Cut

An $s$-$t$ cut partitions the vertices into $S\ni s$ and $T\ni t$; its capacity is the total capacity of edges from $S$ to $T$. The minimum such cut equals the maximum flow.

Max-Flow Min-Cut Theorem

${\max }_{\text{flows}}|f|={\min }_{s\text{-}t\text{ cuts}}c(S,T).$

$\le$: every unit of flow must cross every cut, so any flow is bounded by any cut’s capacity.
$\ge$: at maximum flow, let $S$ be the vertices reachable from $s$ in the residual graph. Then $t\notin S$, every edge $S\to T$ is saturated, and every edge $T\to S$ carries zero flow — so $|f|=c(S,T)$. ∎

Recovering the cut

long long flow = dinic.maxflow(s, t);
vector<bool> inS(n, false);
queue<int> q; q.push(s); inS[s] = true;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int id : g[u])
        if (es[id].cap > 0 && !inS[es[id].to]) { inS[es[id].to] = true; q.push(es[id].to); }
}
// cut edges: original edges (u,v) with inS[u] && !inS[v]

The modelling patterns that matter

Project selection / maximum closure

You may select a set of projects. Project $i$ earns $p_i$ (possibly negative). Selecting $i$ requires selecting $j$. Maximise total profit.

Build: $s\to i$ with capacity $p_i$ for $p_i>0$; $i\to t$ with capacity $-p_i$ for $p_i<0$; $i\to j$ with capacity $\infty$ for each requirement. Then

$\text{answer}={\sum }_{p_i>0}{p}_i-\text{min cut}.$

The infinite edges make it impossible to cut a dependency, so the min cut chooses exactly which profits to forgo and which costs to pay.

Image segmentation / binary labelling

Each pixel gets label A or B. Assigning $i$ to A costs $a_i$, to B costs $b_i$, and neighbouring pixels with different labels cost $w_{ij}$. Build $s\to i$ with $b_i$, $i\to t$ with $a_i$, and undirected $w_{ij}$ between neighbours. The min cut is the optimal labelling — this is exactly the “graph cuts” method from computer vision.

This works because the objective is submodular; general multi-label or non-submodular energies are NP-hard.

Minimum vertex cover in a bipartite graph

By König, it equals the maximum matching. Constructively: run max flow, let $S$ be the residual-reachable set, and the cover is $(L\setminus S)\cup (R\cap S)$.

Others

Problem	Cut formulation
Minimum edges to disconnect $s$ from $t$	unit capacities
Minimum vertices to disconnect $s$ from $t$	split vertices, unit internal capacities (Menger)
Maximum density subgraph	binary search + parametric min cut
Minimum cost to make a grid impassable	planar min cut = shortest path in the dual (Reif)
Partition items into two groups with pairwise penalties	direct min cut

Global min cut — a different problem

“Minimum cut over all pairs $(s,t)$” does not need $n^2$ flow computations:

Algorithm	Time	Type
$n-1$ max flows (fix $s$, vary $t$)	$O(n\cdot \text{maxflow})$	deterministic
Stoer-Wagner	$O(nm+n^2\log n)$	deterministic, ~30 lines
Karger	$O(n^4\log n)$	randomized
Karger-Stein	$O(n^2{\log }^{3}n)$	randomized
Gomory-Hu tree	$n-1$ max flows	gives all pairs min cuts

See Global Min Cut.

Counting min cuts

There are at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ distinct global minimum cuts (a corollary of Karger’s analysis). The number of $s$-$t$ min cuts can be exponential, but they form a lattice: enumerate them from the SCCs of the residual graph — the closed sets of the residual condensation correspond exactly to the minimum cuts.

See also: Maximum Flow · Global Min Cut · Dinic