Karger and the Randomized Minimum-Cut Algorithm

Minimum cut asks for the weakest global separation in a graph

For an undirected graph, a cut partitions the vertices into two groups and counts the edges crossing between them; a global minimum cut is a cut with the smallest such value. NIST defines minimum cut as a smallest edge set whose removal separates vertices.^[1] Classical approaches could derive cuts through flow computations, but David Karger’s work showed that the global undirected problem also admits an astonishingly simple randomized strategy: repeatedly contract randomly selected edges and hope the true minimum-cut edges survive.

Randomness is used to avoid knowing which edges matter

The algorithm does not identify promising edges directly. Instead it relies on the fact that a minimum cut is small relative to the graph’s total edge population at each stage.

Karger’s 1992-1993 contraction algorithm reduced the graph by random merging

Karger’s paper “Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm” presents the contraction idea for weighted undirected graphs and emphasizes its extreme simplicity.^[2] Choose an edge uniformly at random, merge its endpoints into one supervertex, discard self-loops and retain parallel edges. Repeat until only two supervertices remain. The edges between those two final supervertices define a cut of the original graph.

Contraction preserves any cut whose edges are never selected

The key structural fact is straightforward: contracting an edge that does not cross a particular cut merges two vertices on the same side, so that cut remains representable in the smaller graph. Georgia Tech lecture notes on Karger’s algorithm formalize this correspondence.^[3] Therefore, if the algorithm happens never to contract an edge belonging to one fixed minimum cut, that minimum cut survives all the way to the final two supervertices and is returned exactly.

Failure has one identifiable cause

For a chosen minimum cut, the run fails to preserve it precisely when the random process contracts one of that cut’s edges.

The success probability follows from a lower bound on graph density

If the minimum cut has value k, every remaining vertex in an unweighted multigraph must have degree at least k; otherwise that vertex alone would define a smaller cut. This implies the graph has at least nk/2 edges when n supervertices remain. Since only k of those edges cross the target minimum cut, the probability that one random contraction destroys that cut is at most 2/n at that stage. Multiplying the survival probabilities across contractions yields a probability on the order of 1/n² that one run preserves a particular minimum cut.^[2][3]

A small success probability becomes useful because repetition is cheap and independent

A single run is unlikely to succeed on a large graph, but randomized algorithms can amplify success by independent repetition. Run the contraction process many times and keep the smallest cut found. The original contraction analysis and later expositions show how repeated independent trials reduce the probability of missing the optimum.^[2][3] The algorithm is Monte Carlo in the sense that a run can return a nonminimum cut, yet the failure probability can be driven down as far as desired by repeating the experiment.

Randomization converts certainty into a tunable resource

The programmer chooses how much failure probability is acceptable and spends additional runs to reduce that risk.

Karger and Stein improved the contraction strategy by branching before the graph became tiny

The basic algorithm’s success probability drops because the danger of hitting a minimum-cut edge increases as the graph shrinks. Karger and Clifford Stein refined the idea by contracting only to an intermediate size and then recursively branching into multiple independent continuations.^[4] This focuses repetition where it matters most, near the small-graph stages in which survival becomes precarious. Their work improved expected running time substantially while preserving the intuitive contraction framework.

The method helped establish random sampling as a serious graph-algorithm tool

Karger’s later research used random sampling and sparsification for cuts, flows and network-design problems. His 1994 STOC paper showed how sampled subgraphs can approximately preserve cut values and support faster randomized algorithms.^[5] The contraction algorithm therefore mattered beyond one problem. It made randomness feel structural rather than decorative: sampling could expose or preserve global graph properties without explicitly exploring every combinatorial possibility.

Simple random choices can encode sophisticated global search

The algorithm never enumerates cuts. Instead, the contraction process probabilistically eliminates many cuts at once while occasionally leaving a minimum cut intact.

Why Karger’s minimum-cut algorithm belongs in algorithmic history

Karger’s algorithm belongs in history because of the gap between its simplicity and the strength of its analysis. “Pick a random edge and contract it” sounds almost too naive to solve a serious optimization problem, yet a few graph inequalities produce a rigorous success bound.^[2]

The method also changed how students and researchers understand randomized algorithms. Randomness does not have to approximate the objective directly. It can alter the search space so that a desired structure survives with analyzable probability.

That lesson has had wide influence. Random contraction, sampling and sparsification became core graph-algorithm techniques, and Karger’s minimum-cut work remains one of the clearest examples of how probability can replace elaborate deterministic case analysis with a small algorithm and a strong proof.

RESEARCH / PROVENANCE

Works Cited

5 SOURCES

1. 01
   NIST DADS — Minimum Cut ↗nist.gov
2. 02
   David R. Karger — Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm ↗people.csail.mit.edu
3. 03
   Georgia Tech — Lecture Notes on Karger's Min-Cut Algorithm ↗faculty.cc.gatech.edu
4. 04
   Karger and Stein — An O~(n^2) Algorithm for Minimum Cuts ↗doi.org
5. 05
   Karger — Random Sampling in Cut, Flow, and Network Design Problems ↗doi.org

CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.