Karger's Randomized Contraction Algorithm for Min Cut

The problem: cutting a graph in the cheapest place

Given an undirected graph G = (V, E) with n vertices and m edges, a cut is a partition of V into two non-empty sets (S, V∖S). The size of the cut is the number of edges crossing between the two sides (or the sum of edge weights). The global minimum cut is the cut of smallest size over all possible partitions — no fixed source or sink is specified.

This differs from the more familiar s-t min cut, where you must separate two given vertices. The global version asks for the graph's single weakest point: the fewest edges you can delete to break it into two pieces.

• Applications: network reliability (how many links must fail to partition the network), image segmentation, clustering, and VLSI design.
• Classic approach: fix a source s, compute the s-t min cut to every other vertex via max-flow, and take the minimum — n-1 flow computations.

Karger's insight was that you can find this global optimum without computing a single flow, using nothing but random edge contractions.

How it works: random edge contraction

The core operation is edge contraction. To contract edge (u, v): merge u and v into a single super-vertex, redirect every edge that touched u or v to the merged vertex, and delete self-loops (edges that had both endpoints inside the merged set). Crucially, parallel edges are kept — the multiplicity encodes how many original edges cross a boundary, which is what the algorithm counts.

contract(G):
  while G has more than 2 vertices:
    pick edge (u,v) uniformly at random
    merge v into u          # super-vertex
    remove self-loops
  return number of edges between the 2 remaining vertices

mincut(G):        # amplification
  best = infinity
  repeat T = n(n-1)/2 * ln n times:
    best = min(best, contract(copy of G))
  return best

When only two super-vertices remain, every original vertex has been assigned to one side or the other — that partition is a cut, and the surviving edges are exactly the ones crossing it. The algorithm never explicitly tracks the partition; the contraction sequence implicitly builds it.

Why it works: the 2/(n(n-1)) bound

Fix any particular minimum cut C of size k. The algorithm outputs C exactly when it never contracts one of C's k edges. Here is the key fact: if the min cut is k, then every vertex has degree ≥ k, so the graph has at least nk/2 edges. The probability the first random edge lies in C is therefore at most k/(nk/2) = 2/n.

After i successful contractions, n−i super-vertices remain, and the same argument gives failure probability ≤ 2/(n−i) at that step. Multiplying the survival probabilities:

P[C survives] ≥ ∏_{i=0}^{n-3} (1 − 2/(n−i))
            = (n-2)/n · (n-3)/(n-1) · … · 1/3 · (?)
            = 2 / (n(n-1))

So one run succeeds with probability ≥ 2/(n(n-1)) ≈ 2/n². Run it T = (n²/2)·ln n independent times and the chance all fail is ≤ (1 − 2/n²)^T ≤ e^{−ln n} = 1/n. A single run is O(n²) (or O(m) with union-find), so amplified it is O(n⁴ log n). A neat corollary: since distinct min cuts survive disjoint events, a graph has at most n(n-1)/2 = C(n,2) distinct minimum cuts.

Where it shows up in real systems

Karger's contraction is more than a textbook curiosity — its ideas ripple through practical tooling:

• Network reliability & telecom: the global min cut equals the graph's edge connectivity, the minimum number of link failures that can partition a backbone. Karger's later randomized work directly attacks reliability estimation.
• Graph partitioning & clustering: contraction-based coarsening underlies multilevel partitioners like METIS and community-detection heuristics, which repeatedly merge tightly-connected vertices.
• Image segmentation & computer vision: min-cut/normalized-cut formulations separate foreground from background; randomized contraction offers a lightweight alternative to flow solvers on large pixel grids.
• Distributed and streaming settings: because contraction is local and embarrassingly parallel across independent runs, it fits map-reduce and GPU batch execution well.
• VLSI and circuit design: min cuts identify where a netlist can be split across chips or partitions with the fewest crossing wires.

In production, the deterministic Stoer-Wagner algorithm is often preferred for exactness, but Karger's simplicity and parallelizability make it attractive when approximate-but-fast is acceptable, or when you want all near-minimum cuts.

Karger-Stein and the alternatives

The naive O(n⁴ log n) cost comes from a wasteful pattern: most contraction runs fail only in their final few steps, when the surviving edge count is tiny and a min-cut edge is disproportionately likely to be picked. Early steps are almost always safe.

Karger-Stein (1996) exploits this. It contracts the graph down to about n/√2 vertices — where the min cut still survives with probability ≥ 1/2 — then recurses twice on that reduced graph and returns the better result. The recurrence

T(n) = 2·T(n/√2) + O(n²)   ⟹   T(n) = O(n² log n)

and the success probability improves to Ω(1/log n) per run, so O(log² n) runs give high probability, for a total of O(n² log³ n) to find the min cut with high confidence.

• vs Stoer-Wagner: deterministic, O(nm + n² log n), always correct — but harder to parallelize and it finds one min cut, not the structure of all of them.
• vs max-flow (Gomory-Hu): exact and well-understood but heavier; n-1 flow computations.

Pitfalls, failure modes, and significance

It is Monte Carlo, not Las Vegas. A single run can silently return a non-minimum cut, and you cannot cheaply verify optimality — the only remedy is enough independent repetitions. Skimping on T (say, running it O(n) times instead of O(n² log n)) drops the success probability far below any useful threshold.

• Self-loop bug: forgetting to delete self-loops after a merge lets the algorithm contract a phantom edge and corrupts the count. Parallel edges, by contrast, must be preserved — collapsing them into one edge silently biases the random selection.
• Weighted graphs: select an edge with probability proportional to its weight, not uniformly; treat a weight-w edge as w parallel edges conceptually.
• Directed graphs: the algorithm is undefined for them — global min cut in digraphs needs different tools.

Its significance is conceptual as much as practical: it showed that a problem long solved only via heavyweight flow theory has a two-line randomized solution, and its analysis directly proves the beautiful combinatorial bound that any graph has at most C(n,2) minimum cuts.

Global min-cut approaches: complexity and characteristics

Algorithm	Time complexity	Type	Note
Karger (single run)	O(n²)	Monte Carlo	Correct with prob ≥ 2/(n(n-1))
Karger, amplified	O(n⁴ log n)	Monte Carlo	O(n² log n) runs for high probability
Karger-Stein	O(n² log n)	Monte Carlo	Recursive contraction; prob Ω(1/log n)/run
Stoer-Wagner	O(nm + n² log n)	Deterministic	Maximum-adjacency ordering, no flow
Gomory-Hu / max-flow	O(n · maxflow)	Deterministic	n-1 s-t min-cut computations