Resources

The resources below include many clever applications of min cut, including the Closure Problem.

Min-Cut Max-Flow Theorem

Given a flow network with source $s$ and sink $t$, an $s$-$t$ cut is a partition of the vertices into two sets $S$ and $T$ with $s \in S$ and $t \in T$. Its capacity is the total capacity of the edges crossing from the source side to the sink side:

(Edges pointing the other way, from $T$ to $S$, contribute nothing.) Cutting all of these edges disconnects $s$ from $t$, so intuitively the capacity of a cut is an upper bound on how much flow can get from $s$ to $t$. Indeed, for any flow $f$ and any cut $(S, T)$,

where $\operatorname{val}(f)$ is the total flow from $s$ to $t$. So every flow is bounded by every cut.

Here is an illustration of a $s-t$ cut: red nodes are in $S$, and blue nodes are in $T$. Importantly, there is no need for $S$ and $T$ to be connected: the only requirement is that $s \in S$ and $t \in T$. The capacity of this cut is the sum of the capacities underlined in green, $2 + 1 = 3$. The flow across this cut derives from the numbers underlined in yellow, $2 - 1 + 1 = 2$, which we note is equivalent to the actual $s-t$ flow, $\operatorname{val}(f)$. Also note that in this instance, the flow across the cut ($2$) is less than its capacity ($3$). However, if we instead choose $S = \{s\}$ and $T = V \setminus \{s\}$, the flow across the cut ($2$) and its capacity ($2$) will be equal.

The min-cut max-flow theorem states that in general, we can always achieve such equality:

The maximum value of an $s$-$t$ flow equals the minimum capacity of an $s$-$t$ cut.

To show tightness, we just need to construct a flow $f$ and cut $(S, T)$ such that $\operatorname{val}(f) = \operatorname{cap}(S, T)$. To do this, we will let $f$ be any maximum flow, then use the fact that $f$ cannot have any remaining augmenting paths to construct a minimum capacity $(S, T)$ cut. In fact, it turns out this cut can be constructed by letting $S$ be the set of nodes reachable from $S$ in the residual graph (and $T$ be the set of all other nodes, i.e. $V - S$). To see why this is the case, consider the following diagram:

By definition, the red edges must be saturated to capacity, otherwise nodes in $S$ would be able to reach nodes in $T$. Similarly, the blue edges must have 0 flow. Therefore, the flow across this cut equals the capacity of this cut, as desired.

Minimum Node Covers

Solution - Coin Grid

This problem asks us to find a minimum node cover of a bipartite graph. Construct a flow graph with vertices labeled $0\ldots 2N+1$, source $0$, sink $2N+1$, and the following edges:

• Edges from $0\to i$ with capacity $1$ for each $1\le i\le N$. Cutting the $i$-th such edge corresponds to choosing the $i$-th row.
• Edges from $N+i\to 2N+1$ with capacity $1$ for each $1\le i\le N$. Cutting the $i$-th such edge corresponds to choosing the $i$-th column.
• If there exists a coin in $(r,c)$ add an edge from $r\to N+c$ with capacity $\infty$.

First we find a max flow, which tells us the number of edges with capacity 1 we need to cut. To find the min cut itself, BFS from the source once more time. Edges $(a,b)$ connecting vertices that are reachable from the source (lev[a] != -1) to vertices that aren't (lev[b] == -1) are part of the minimum cut. In this case, each of these edges must be of the form $(0,i)$ or $(i+N,2N+1)$ for $1\le i\le N$. Each cut edge corresponds to a row or column we remove coins from.

Note that edges of the form $r\to N+c$ can't be cut because they have capacity $\infty$.

Copy
struct Dinic {     // flow template
	using F = ll;  // flow type
	struct Edge {
		int to;
		F flo, cap;
	};
	int N;
	V<Edge> eds;
	V<vi> adj;
	void init(int _N) {

Minimum Path Covers

Solution - The Wrath of Kahn

Ignore all vertices of $G$ that can never be part of $S$. Then our goal is to find the size of a maximum antichain in the remaining graph, which as mentioned in CPH is just an instance of minimum path cover.

Copy
TopoSort<500> T;
int n, m;
bool link[500][500];
vi out[500];
Dinic<1005> D;

int main() {
	setIO();
	re(n, m);
	F0R(i, m) {

Problems