# Minimum Cut

Author: Benjamin Qi

### Prerequisites

?

## Resources

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

Resources | |||
---|---|---|---|

CPC | Slides from "Algorithm Design." Min-Cut Max-Flow Theorem, applications of flow / min cut. |

## Minimum Node Covers

Focus Problem – read through this problem before continuing!

Resources | |||
---|---|---|---|

CPH | brief mentions of Hall's Theorem, Konig's Theorem |

### 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…2N+1$, source $0$, sink $2N+1$, and the following edges:

- Edges from $0→i$ with capacity $1$ for each $1≤i≤N$. Cutting the $i$-th such edge corresponds to choosing the $i$-th row.
- Edges from $N+i→2N+1$ with capacity $1$ for each $1≤i≤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→N+c$ with capacity $∞$.

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≤i≤N$. Each cut edge corresponds to a row or column we remove coins from.

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

struct Dinic { // flow templateusing F = ll; // flow typestruct Edge { int to; F flo, cap; };int N; V<Edge> eds; V<vi> adj;void init(int _N) { N = _N; adj.rsz(N), cur.rsz(N); }/// void reset() { trav(e,eds) e.flo = 0; }void ae(int u, int v, F cap, F rcap = 0) { assert(min(cap,rcap) >= 0);adj[u].pb(sz(eds)); eds.pb({v,0,cap});adj[v].pb(sz(eds)); eds.pb({u,0,rcap});}

## Minimum Path Covers

Focus Problem – read through this problem before continuing!

Resources | |||
---|---|---|---|

CPH | brief mentions of node-disjoint and general path covers, Dilworth's theorem | ||

Wikipedia | proof via Konig's theorem |

### 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.

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) {int x,y; re(x,y);

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

CSES | Easy | View Solution | ||||

Old Gold | Easy | ## Show TagsMax Flow | External Sol | |||

CSA | Normal | Check CSA | ||||

CF | Normal | Check CF | ||||

CF | Normal | Check CF | ||||

CF | Hard | Check CF | ||||

AC | Hard | Check AC | ||||

FHC | Hard | Check FHC |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

## Give Us Feedback on Minimum Cut!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.