Minimum Cut

Resources

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

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\dots 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$.

1struct Dinic { // flow template
2    using F = ll; // flow type
3    struct Edge { int to; F flo, cap; };
4    int N; V<Edge> eds; V<vi> adj;
5    void init(int _N) { N = _N; adj.rsz(N), cur.rsz(N); }
6    /// void reset() { trav(e,eds) e.flo = 0; }
7    void ae(int u, int v, F cap, F rcap = 0) { assert(min(cap,rcap) >= 0); 
8        adj[u].pb(sz(eds)); eds.pb({v,0,cap});
9        adj[v].pb(sz(eds)); eds.pb({u,0,rcap});
10    }

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 maximum path cover.

1TopoSort<500> T;
2int n,m;
3bool link[500][500];
4vi out[500];
5Dinic<1005> D;
6
7int main() {
8    setIO(); re(n,m);
9    F0R(i,m) {
10        int x,y; re(x,y);

Problems