Minimum Cut

A minimum cut is the cheapest set of edges whose removal disconnects the sink from the source in a flow network. The max-flow min-cut theorem states its capacity equals the maximum flow, so computing one solves the other.

How it works

After running any maximum flow algorithm, the minimum cut is recovered by finding all vertices still reachable from the source in the residual graph; every full edge from that reachable set to the rest is a cut edge. For global minimum cuts without a fixed source and sink, the Stoer-Wagner algorithm contracts vertices in O(V cubed) time and Karger's randomized contraction gives an elegant probabilistic alternative.

Applications

Minimum cuts identify network bottlenecks and vulnerabilities, split images into foreground and background in computer vision, partition circuits in VLSI design, and measure community boundaries in social networks. Understanding the duality with max flow is a hallmark of strong algorithm candidates.