A min cut (short for minimum cut) is the smallest set of edges you need to remove from a graph to split it into two separate, disconnected groups of nodes. If the edges have weights or capacities, the min cut is the partition where the total weight of the removed edges is as low as possible. It’s one of the foundational concepts in graph theory and shows up in everything from network design to image processing.
How a Cut Works in a Graph
A graph is a collection of nodes (also called vertices) connected by edges. Think of cities connected by roads, or computers connected by cables. A “cut” is any way of dividing all the nodes into two groups, then looking at which edges cross between those groups. Those crossing edges form the cut.
More precisely, you pick some subset S of nodes. Every edge that has one endpoint inside S and the other endpoint outside S belongs to the cut. If each edge carries a cost or capacity, the cost of that cut is the sum of those edge weights. The minimum cut is simply the division that makes this total as small as possible.
One important detail: only cuts where both sides remain internally connected can be minimum cuts (assuming all edge weights are positive). If one side of your partition is broken into disconnected pieces, you could merge some of those pieces back together and get a cheaper cut.
Global Min Cut vs. Source-Sink Cut
There are two flavors of the min cut problem, and they come up in different contexts.
A global min cut asks: what is the cheapest way to split an undirected graph into any two non-empty groups? There’s no constraint on which nodes end up on which side. You’re just looking for the weakest point in the entire graph.
A source-sink (s-t) cut is more specific. You pick two designated nodes, a source s and a target t, and require that s ends up on one side of the partition and t on the other. This version uses directed graphs, where edges flow in one direction, and it connects directly to network flow problems.
You can actually find a global min cut by solving the s-t version repeatedly. Fix one node as the source, then compute the minimum s-t cut for every other node as the target. The cheapest result across all those runs is the global min cut. That takes n-1 flow computations for a graph with n nodes. For a long time, this made people assume global min cuts were inherently harder to find than s-t cuts. But algorithms developed in the late 1980s and 1990s showed that global min cuts can be computed just as efficiently, or even faster, using techniques that don’t involve flow at all.
The Max-Flow Min-Cut Theorem
The most famous result connecting min cuts to the rest of computer science is the max-flow min-cut theorem. It says: in any flow network with a source and a target, the maximum amount of flow you can push from source to target exactly equals the capacity of the minimum s-t cut.
This is intuitive if you think about it physically. Imagine water flowing through a network of pipes. The bottleneck that limits total flow is the narrowest “slice” across the network, the place where total pipe capacity is lowest. That bottleneck is the min cut. No matter how cleverly you route the water, you can never push more through than what that narrowest slice allows. And with the right routing, you can always achieve exactly that amount.
This duality means that solving a max-flow problem automatically gives you the min cut, and vice versa. Any flow that matches the capacity of some cut must be the maximum flow, and that cut must be the minimum cut.
Algorithms for Finding Min Cuts
Several well-known algorithms can find min cuts, each with different tradeoffs.
For s-t cuts, any max-flow algorithm works. You compute the maximum flow, then identify the edges that are fully saturated. The saturated edges on the source side of the bottleneck define the min cut.
For global min cuts, one elegant approach is Karger’s randomized contraction algorithm. The idea is simple: repeatedly pick a random edge and merge its two endpoints into a single node, collapsing the graph until only two nodes remain. The edges between those two remaining nodes represent a cut. A single run of this contraction takes roughly n² operations for a graph with n nodes, but it only finds the true min cut with probability at least 2/n². That’s low, but you can boost your odds by repeating the process many times. The improved Karger-Stein version runs in O(n² log n) time and succeeds with much higher probability, around 1/log n per run. Running it O(log² n) times brings the failure rate down to negligibly small.
The fastest known deterministic algorithms for global min cut now run in near-linear time, meaning roughly proportional to the number of edges in the graph times some small logarithmic factors.
Image Segmentation
One of the most striking real-world uses of min cuts is separating objects from backgrounds in images. The basic setup, developed extensively in computer vision research at CMU and elsewhere, works like this.
Each pixel in an image becomes a node in a graph. Neighboring pixels are connected by edges. Two special nodes are added: a “source” representing the foreground and a “sink” representing the background. Every pixel gets an edge to the source (weighted by how likely it is to be foreground) and an edge to the sink (weighted by how likely it is to be background). The edges between neighboring pixels carry a penalty for separating them, so that the algorithm prefers to keep similar-looking pixels on the same side.
Finding the min cut of this graph partitions every pixel into either foreground or background. Pixels on the source side become foreground; pixels on the sink side become background. The min cut naturally balances three competing goals: assign pixels to the label they most likely belong to, keep neighboring pixels together, and only separate neighbors when the evidence is strong enough to justify the penalty. Because a brown pixel near other brown pixels on a football is likely foreground, the algorithm clusters them together. Because the cut penalty discourages jagged boundaries, the resulting segmentation tends to follow natural edges in the image.
Network Vulnerability Analysis
Min cuts also reveal the weakest points in real infrastructure. In a transportation or communication network, the min cut identifies the smallest set of links whose failure would disconnect part of the network from the rest. This makes it a natural tool for vulnerability analysis.
Researchers have applied min cut methods to road networks, for instance computing all minimum cuts between pairs of cities in Japan’s central region to identify the most critical road segments. Two types of vulnerability matter here: the raw capacity of a cut (how much traffic the severed links could carry) and the actual demand passing through those links (how many people rely on them daily). A cut might have high capacity but carry little traffic, or low capacity but serve as the only connection between major population centers. Both dimensions matter for infrastructure planning and disaster preparedness.
The same logic applies to computer networks, power grids, and supply chains. Anywhere you have a network and want to know where it’s most fragile, the min cut gives a precise, computable answer.