---
title: "Min-Cut Models"
summary: Seven reductions where the answer of a combinatorial problem is exactly a minimum cut — maximum closure, bipartite covering, project selection, and the submodular energy.
difficulty: hard
tags: [flow, modelling, duality]
prereq: [flow/maxflow]
see: [matching/konig, foundations/connectivity]
---

:::definition label="Closure"
In a digraph, a set $S$ is a **closed set** (down-set) if $u \in S$ and $u \to v$ imply $v \in S$. The *maximum weight closure* problem: maximise $\sum_{v \in S} w_v$ over closed $S$, with weights of both signs.
:::

:::theorem title="Closure = min cut"
Build $s \to v$ with capacity $w_v$ for $w_v > 0$; $v \to t$ with capacity $-w_v$ for $w_v < 0$; every original edge $u \to v$ with capacity $\infty$. Then
$$\max_{\text{closed } S} \sum_{v\in S} w_v = \sum_{w_v > 0} w_v - \min\text{-cut},$$
and the optimal $S$ is the source side of the min cut.
:::

:::proof
For any cut $(A, \bar A)$ with $s \in A$, $t \notin A$, put $S = A \setminus \{s\}$. If $S$ is not closed, some edge $u \to v$ leaves $S$ (u in, v out), contributing $\infty$ — so finite cuts are exactly the closed sets. For a closed $S$, the cut pays: (i) each positive $w_v$ with $v \notin S$ (the edge $s \to v$ is cut), and (ii) each $|w_v|$ with $v \in S$ (the edge $v \to t$ is cut). So
$$c(S) = \sum_{w_v>0, v\notin S} w_v + \sum_{w_v<0, v\in S} (-w_v) = \sum_{w_v > 0} w_v - \sum_{v \in S} w_v,$$
which is minimised exactly when the closure's weight is maximised. ∎
:::

:::props title="The catalogue (each is the same three lines)"
- **Project selection**: profit $p_i$, cost $c_j$ of prerequisites ⇒ closure with weights $p_i - c_j$. Add "$\infty$" 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 \to r$ with $\infty$, then $s\to l$ (weight), $r\to t$ (weight) — the $\infty$ edges forbid "both endpoints kept" exactly as needed; complements turn a cover into an independent set (@matching/konig).
- **Minimum vertex cover in bipartite graphs** (unweighted): source → left (cap 1), matching edges left→right ($\infty$), 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$** (@foundations/connectivity): unit capacities on edges, or vertex-splitting $v_{in}\to v_{out}$ with capacity 1 for vertices.
- **Maximum density subgraph / fractional covering**: parametric min cut — binary search $\lambda$, solve "is there $S$ with $\sum_{v\in S}(w_v - \lambda) > 0$?" as a closure, $O(\log)$ max-flow runs.
- **Binary energy minimisation**: variables $x_i \in \{0,1\}$, unary terms go on $s$-/$t$-edges, a pairwise term $V_{ij}(0,1)+V_{ij}(1,0) \ge V_{ij}(0,0)+V_{ij}(1,1)$ (submodularity) becomes one edge of capacity $\frac{V_{ij}(0,1)+V_{ij}(1,0)-V_{ij}(0,0)-V_{ij}(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 (@matching/bipartite).
:::

:::note title="Recognising the pattern in a statement"
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 $\sum$ (kept profits) $- \sum$ (penalties) and ask: which constraint becomes an $\infty$ edge?
:::

:::warning title="Capacity of ∞ must be big, not maximal"
Use $\infty = 1 + \sum |w|$ (or $10^{15}$ 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\times10^{12}$ in the *wrong* type. Also: if the min cut you get has value $\ge \infty$, your model is wrong — a finite cut must always exist (e.g. take all positive vertices, if that is closed).
:::

:::example title="Reading the *specific* answer out of the cut"
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 \leadsto v$ in the residual graph; $v$ is in **no** min cut iff $v \leadsto t$. To enumerate all min cuts, condense the residual graph — the min cuts are the closed sets of the condensation separating $\operatorname{scc}(s)$ from $\operatorname{scc}(t)$ (@flow/maxflow's lattice remark).
:::

:::problems
- [[CSES 1695]] Police Chase | https://cses.fi/problemset/task/1695 | core | the min cut is the minimum set of roads to close — read it off the residual graph
- [[CSES 2130]] Distinct Routes II | https://cses.fi/problemset/task/2130 | hard | vertex-disjoint paths: vertex splitting turns "delete a vertex" into a unit-capacity cut
:::