Karger's Algorithm

Karger's algorithm is a randomized Monte Carlo algorithm within computation and algorithms that computes the global minimum cut of a connected undirected multigraph G = (V, E) by iteratively selecting edges uniformly at random and contracting their endpoints until only two supervertices remain. Introduced by computer scientist David R. Karger in 1993, the algorithm demonstrated that global minimum cuts can be found without computing maximum network flows or deterministic maximum adjacency orderings such as the Stoer–Wagner algorithm.

Because a minimum cut contains far fewer edges than the average vertex degree across the graph, a uniformly chosen random edge is unlikely to belong to a specific minimum cut during the early stages of contraction. Using a telescoping product of conditional survival probabilities, Karger proved that a single contraction trial preserves any particular global minimum cut with probability at least 2 / (n(n − 1)) = 1 / C(n, 2), which simultaneously yields an elegant probabilistic proof that an undirected graph on n vertices can have at most n(n − 1) / 2 distinct global minimum cuts. Furthermore, by branching recursively when the remaining vertex count reaches n / √2, the Karger–Stein algorithm (Karger & Stein, 1996) reduces the time required to find a global minimum cut with high probability from O(n²m log n) to O(n² log³ n).

The Elementary Contraction Step

Let G = (V, E) be a connected undirected multigraph with n = |V| vertices and m = |E| edges (for edge-weighted graphs, each edge is sampled with probability proportional to its positive weight w(e)). Contracting an edge e = {u, v} merges vertices u and v into a single supervertex uv, retains all parallel edges between uv and other vertices w ∉ {u, v}, and deletes all self-loops between u and v.

A single run of Karger's basic contraction procedure executes n − 2 random edge contractions:

1. While |V| > 2, pick an edge e ∈ E uniformly at random (or proportional to weight w(e)).
2. Contract edge e in G, reducing |V| by 1 and removing any resulting self-loops.
3. When |V| = 2, return the cut (S, V_orig \ S) defined by the two remaining supervertices.

Telescoping Proof of the ≥ 2 / (n(n − 1)) Bound

Fix any specific global minimum cut C = (S, V \ S) of G containing k = |C| edges. Notice that every contraction preserves the cut C as long as no edge belonging to C is ever selected for contraction. Suppose the algorithm has completed i contractions without contracting any edge of C, leaving a contracted multigraph G_i on n_i = n − i supervertices.

Because every single supervertex in G_i defines a valid cut in the original graph G—and C is a global minimum cut of size k—every supervertex v ∈ V(G_i) must have degree at least k in G_i. By the handshaking lemma, the total number of edges remaining in G_i satisfies:

Therefore, at step i, the conditional probability that a uniformly chosen random edge in G_i belongs to the k edges of C is at most:

Multiplying the complementary survival probabilities 1 − 2/(n − i) = (n − i − 2)/(n − i) across all n − 2 contraction steps (from i = 0 to i = n − 3) produces a telescoping product:

Extremal Corollary: At Most C(n, 2) Global Minimum Cuts

Because Karger's algorithm outputs a single cut at the end of a run, the events {algorithm outputs C_j} are mutually exclusive across all distinct global minimum cuts C₁, C₂, …, C_r of G. Since each individual minimum cut C_j is returned with probability at least 2 / (n(n − 1)) and the sum of probabilities of mutually exclusive events cannot exceed 1, it follows that r ≤ n(n − 1) / 2 = C(n, 2). This bound is tight: an unweighted n-vertex cycle graph C_n has minimum cut size k = 2, and choosing any 2 of its n edges yields one of the C(n, 2) distinct minimum cuts.

Why Late Contractions Dominate Failure Probability

Inspecting the conditional failure probability 2 / (n − i) reveals an asymmetry between early and late contractions: when the graph still has n vertices, the first contraction fails with probability at most 2/n (very safe), whereas when only 3 supervertices remain, the final contraction fails with probability up to 2/3. If the contraction process is halted early when t supervertices remain, the telescoping product from n down to t evaluates to:

Setting the stopping threshold to t = ⌈1 + n / √2⌉ guarantees that C survives down to t vertices with probability ≥ 1/2!

Recursive Binary Branching (FastCut)

David Karger and Clifford Stein (1996) exploited this 1/2 survival threshold in their FastCut(G) algorithm:

1. If |V| ≤ 6, compute the minimum cut of G directly by brute-force enumeration in O(1) time.
2. Otherwise, set t ← ⌈1 + |V| / √2⌉.
3. Perform two independent partial contractions of G from |V| down to t vertices, yielding contracted multigraphs H₁ and H₂, each taking O(|V|²) time.
4. Recursively compute C1 ← FastCut(H1) and C2 ← FastCut(H2), and return the smaller of the two cuts.

Because each of the two branches preserves C down to size n / √2 with probability ≥ 1/2, the recurrence for the runtime T(n) and the success probability P(n) across depth log_√2 n = 2 log₂ n satisfies:

Repeating FastCut(G) O(log² n) independent times amplifies the overall failure probability to (1 − Θ(1 / log n))^{c log2 n} ≤ 1 / n^c, finding the global minimum cut with high probability in O(n² log³ n) total time.

Karger's O(m log³ n) Tree-Packing Algorithm (2000)

In 2000, Karger achieved a near-linear O(m log³ n) randomized global minimum cut algorithm by combining random edge sampling (graph sparsification) with Tutte–Nash-Williams greedy spanning tree packing. Karger showed that in a packed collection of O(log n) weight-disjoint spanning trees of a sparsified graph, at least one spanning tree T 2-respects the global minimum cut (meaning the minimum cut crosses at most 2 edges of T), allowing dynamic programming on tree paths to evaluate all 1-respecting and 2-respecting cuts of T in O(m log² n) time.

Enumerating All Minimum and Near-Minimum Cuts

Unlike deterministic algorithms such as the Stoer–Wagner algorithm, which return only a single minimum cut, running the Karger–Stein algorithm O(n² log n) times enumerates all global minimum cuts of G with high probability, and stopping the contraction at t = 2α vertices enumerates all α-approximate minimum cuts (cuts of weight ≤ α · λ(G), of which there are at most O(n^2α)) for network reliability polynomials, parallel Borůvka's algorithm MST verification, and phylogenetic supertree quartet cutting.

How can random edge contractions be implemented using a disjoint-set (Union–Find) structure?

For an unweighted graph, generating a uniformly random permutation of all m edges in O(m) time (via Fisher–Yates shuffle) and scanning the shuffled edges while merging their endpoints in a disjoint-set data structure until 2 components remain is mathematically equivalent to repeatedly picking a random non-self-loop edge in the contracted multigraph! This Kruskalian permutation implementation runs a full contraction trial in O(m α(n)) time without explicitly mutating adjacency lists.

What is the difference between a Monte Carlo algorithm like Karger's and a Las Vegas algorithm?

A Las Vegas randomized algorithm (such as randomized Quicksort or a treap) always produces a 100% guaranteed optimal output, with only its runtime being a random variable. By contrast, Karger's algorithm is a Monte Carlo randomized algorithm: its runtime is deterministic for a fixed number of trials, and it always outputs a valid cut of G, but with a small, tunable probability ≤ 1/n^c the returned cut may have weight larger than the true global minimum cut (a one-sided error).

Why does Karger's algorithm fail if we pick two vertices uniformly at random to merge instead of picking a random edge?

If two vertices u and v were selected uniformly at random regardless of how many edges connect them, a degree-1 leaf vertex attached by a single bridge edge would be merged with an unrelated vertex just as often as two densely connected core vertices. Only by sampling an edge with probability proportional to its weight (so heavily connected vertex pairs are merged with proportionally higher probability) does the failure probability at step i stay bounded by k / |E(G_i)| ≤ 2 / (n − i).

1. Karger, D. R. (1993). "Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm." In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '93), 21–30. https://dl.acm.org/doi/10.5555/313559.313605
2. Karger, D. R., & Stein, C. (1996). "A new approach to the minimum cut problem." Journal of the ACM, 43(4), 601–640. https://doi.org/10.1145/234533.234534
3. Karger, D. R. (2000). "Minimum cuts in near-linear time." Journal of the ACM, 47(1), 46–76. https://doi.org/10.1145/331605.331608
4. Motwani, R., & Raghavan, P. (1995). Randomized Algorithms (Section 1.1 & Chapter 10: Graph Algorithms and Min-Cut). Cambridge University Press. https://doi.org/10.1017/CBO9780511814075