A Bit of History
David Karger developed the random-contraction approach in the early 1990s. Its lasting appeal is not that randomness magically makes every run correct; it is that a three-line idea admits a sharp, useful success bound. The algorithm became a canonical example of how independent repetition can convert a weak randomized primitive into a dependable method.
Karger and David Stein later improved the strategy by contracting only partway, branching recursively, and avoiding the cost of restarting every trial from the original graph. The basic algorithm remains the best place to learn the probability argument.
The Global-Cut Goal
For an undirected multigraph, a cut partitions the vertices into two non-empty sets. Its size is the number of edge copies crossing between the sets. The global minimum cut is the partition with the fewest crossing edges.
Parallel edges are not cosmetic: two copies represent two units of connectivity and count twice in the cut. For non-negative integer capacities, an edge of capacity $c$ can be viewed as $c$ parallel copies. More generally, weighted contraction samples an edge with probability proportional to its capacity; the implementations below focus on the explicit unweighted multigraph model.
Sample edge copies
Every current non-loop edge occurrence must have equal probability—not every vertex or distinct endpoint pair.
Multiplicity is capacity
Contraction can create several edges between two super-vertices. Retain every copy.
Internal edges vanish
An edge whose endpoints have merged can cross no future cut, so it may be discarded.
Algorithm Overview
- Start with the current multigraph. Each vertex initially represents only itself.
- Choose one current edge uniformly at random. If parallel edges exist, each copy is a separate lottery ticket.
- Contract its endpoints. Unite the represented vertex groups, keep incident parallel edges, and remove newly created self-loops.
- Continue until two super-vertices remain. Their represented groups form a cut; the surviving edges between them are its size.
- Repeat independently. Return the smallest cut observed across all trials.
What Contraction Really Means
Contracting $u$ and $v$ declares that this run will never separate them. The new super-vertex represents the union of their original vertex sets. Any edge from either endpoint to a third vertex remains attached to the super-vertex; if both endpoints had such edges, parallel copies result. The edge $uv$ itself becomes a self-loop and disappears.
The Irreversible Choice
If a run contracts an edge belonging to a particular minimum cut, that cut can never be returned: its endpoints are now forced onto the same side. Success means avoiding every edge of at least one global minimum cut until only its two sides remain.
Visual Walkthrough
The multigraph below contains two dense triples joined by only two crimson edges. Each blue internal connection represents two parallel edge copies. The cluster boundary therefore has size $2$, while isolating any single vertex costs at least four edges.
The Survival-Probability Argument
Fix one particular global minimum cut containing $k$ edge copies. Suppose the current contracted graph has $r$ super-vertices and the fixed cut has survived so far. Every vertex has degree at least $k$; otherwise isolating a lower-degree vertex would yield a cut smaller than the global minimum. By the handshake lemma, the graph therefore has at least $rk/2$ edges.
The probability that the next uniformly sampled edge belongs to our fixed cut is at most
$$\frac{k}{rk/2}=\frac{2}{r},$$
so the conditional probability of preserving it for the next step is at least $(r-2)/r$. Multiplying from $r=n$ down to $r=3$ telescopes:
$$\Pr[\text{one run preserves this cut}]\geq\prod_{r=3}^{n}\frac{r-2}{r}=\frac{2}{n(n-1)}=\binom{n}{2}^{-1}.$$
If the fixed cut survives every contraction, the final two super-vertices are precisely its two sides, so the run returns that minimum cut. Multiple distinct optimum cuts can only improve the chance of returning some optimum beyond this worst-case bound.
From One Lucky Run to High Confidence
Let $p=2/[n(n-1)]$ be the guaranteed per-trial success probability. With $T$ independent trials, the probability that all of them fail is at most
$$\Pr[\text{failure after }T]\leq(1-p)^T\leq e^{-pT}.$$
To target failure probability at most $\delta$, choose
$$T\geq\frac{\ln(1/\delta)}{p}=\frac{n(n-1)}{2}\ln\!\left(\frac1\delta\right).$$
Confidence is a parameter, not a feeling. Choose an acceptable failure probability $\delta$, compute the corresponding trial count, and use independent random choices—or independent seeded streams—across trials.
Complexity Analysis
The transparent edge-list implementations below rebuild the list of currently crossing edges at each contraction. With $m$ original edge copies, one trial costs $O(nm)$ time and $O(n+m)$ auxiliary space. Across $T$ trials:
$$\text{Time: }O(Tnm) \qquad \text{Space: }O(n+m).$$
More specialized multigraph data structures can reduce the work per trial; the basic algorithm is often summarized as $O(n^2)$ per run under a suitable implementation. Achieving failure at most $1/n$ needs $T=O(n^2\log n)$ trials from the worst-case bound. Karger–Stein improves the overall expected running time to $O(n^2\log^3 n)$ by contracting only to roughly $n/\sqrt2$ vertices before branching recursively.
Implementation
The reference versions favor clarity: at each contraction they explicitly rebuild the list of edge copies whose endpoints are still in different components, then sample uniformly from that list. They return one observed partition as well as its cut size, detect disconnected graphs, and allow deterministic seeds for tests.
Choosing a Global Min-Cut Algorithm
| Method | Guarantee | Main idea | Trade-off |
|---|---|---|---|
| Basic Karger | Monte Carlo; exact when successful | Contract random edges to two groups | Beautifully simple, but needs many trials |
| Karger–Stein | Randomized with amplification | Contract partway, then branch recursively | Better asymptotics, more involved implementation |
| Stoer–Wagner | Deterministic and exact | Maximum-adjacency phases and safe contractions | Predictable result; designed for non-negative weighted undirected graphs |
| Repeated max flow | Deterministic and exact | Fix one source and test all other sinks | Useful when a mature max-flow routine already exists |
Karger's strongest systems advantage is trial independence. Runs can be distributed across cores or machines, and only the best result needs to be reduced. That does not automatically make the basic algorithm fastest; graph size, representation, trial budget, and the availability of deterministic solvers all matter.
Where Random Contraction Helps
Probability intuition
A compact case study in conditional probability, telescoping products, and amplification.
Parallel trials
Independent runs require almost no coordination until their final cut values are compared.
Exact baselines
With a stated confidence budget, test graph heuristics against a simple randomized exact-cut candidate.
Network resilience
Estimate the weakest undirected separation, provided the probability of error is acceptable.
Cut discovery
Random contraction can expose sparse boundaries without selecting terminals in advance.
Algorithm design
The survival proof illustrates how preserving one hidden witness can certify a randomized algorithm.
Limitations and Common Pitfalls
| Mistake | Why it matters | Defensive practice |
|---|---|---|
| Choosing a random vertex pair | Endpoint pairs with many parallel edges become underweighted. | Sample uniformly from current edge copies. |
| Collapsing parallel edges | Changes both cut sizes and future sampling probabilities. | Preserve multiplicity; represent capacity by copies or weighted sampling. |
| Keeping self-loops | Wastes samples on edges that can never cross a future cut. | Discard or skip edges whose endpoints share a super-vertex. |
| Running only a handful of trials | The worst-case one-run probability is only $\Theta(1/n^2)$. | Derive $T$ from an explicit failure budget $\delta$. |
| Using correlated “independent” runs | The amplification formula may no longer apply. | Use a sound generator and independent streams; record seeds for reproducibility. |
| Assuming a reported cut is certified optimal | A Monte Carlo run can return a larger cut without warning. | State confidence or verify with a deterministic algorithm when certainty is required. |
| Ignoring disconnected graphs | Contraction can stall before reaching two groups. | Detect components first; disconnected graphs have cut value zero. |
| Expecting a balanced or semantic split | Global min-cut may isolate one low-degree vertex. | Use balanced-cut, conductance, or domain-specific objectives when appropriate. |
Monte Carlo Means One-Sided Error Here
Every returned partition is a real cut, so its size can never be smaller than the true optimum. The error is only that all trials may miss the optimum and return something too large. More independent trials can improve the answer; they can never invalidate a smaller cut already found.
Exercises
Make the Randomness Measurable
- Trace. On the illustrated multigraph, mark which first-edge choices immediately destroy the highlighted cut and compute that probability.
- Derive. Expand the telescoping product $(1-2/n)(1-2/(n-1))\cdots(1-2/3)$ and show that only $2/[n(n-1)]$ remains.
- Budget. For $n=50$ and target failure probability $10^{-6}$, compute the required trial count using the displayed formula.
- Test. Enumerate every non-trivial partition of small random multigraphs. Confirm that every returned cut is valid and that high-confidence runs match brute force.
- Weights. Adapt the Python sampler to edges $(u,v,c)$ by selecting with probability proportional to positive capacity $c$.
- Challenge. Implement Karger–Stein: contract independently to $\lceil n/\sqrt2\rceil+1$ vertices in two branches, recurse, and keep the smaller result.
Hint for 1: count edge copies, not drawn endpoint pairs; the six thick blue links each represent two lottery tickets.