↩ back to Network Flow

Karger's Algorithm

Every other Network Flow entry on this site answers a question about two designated nodes: how much can flow from a fixed source to a fixed sink (Edmonds-Karp, Dinic's, Push-Relabel), or the cheapest way to pair things up (Hungarian Algorithm, Bipartite Matching, Hopcroft-Karp, Minimum-Cost Maximum Flow). The global minimum cut problem drops the source and sink entirely: given an undirected graph, what's the fewest edges whose removal splits it into two disconnected pieces, over every possible way to split it, not just one fixed pair of endpoints? It's a genuinely different question — "where is this network weakest, period" rather than "how much can get between these two specific points."

One way to answer it reuses machinery this site already has: fix any single node s, run a max-flow min-cut computation from s to every other node in turn, and take the smallest result — a theorem guarantees the true global minimum cut shows up as the min s-t cut for some choice of t, so n − 1 max-flow runs, deterministic, always correct. Karger's algorithm, published by David Karger in 1993, answers the same question a completely different way: no source, no sink, no residual graph — just repeatedly pick a uniformly random remaining edge and merge (contract) its two endpoints into one, until only two "super-nodes" are left. The edges still connecting those two super-nodes form a cut. It's randomized, not exact — a single run can and does return a cut that's larger than the true minimum — but it's simpler to implement than any max-flow method, and repeating it enough times to reach a wanted confidence turns out to be cheaper on dense graphs than the deterministic approach. It's also this site's first genuinely randomized network-flow answer, in the same family as Skip List or Treap rather than the deterministic six entries above.

Try it

Six nodes: a triangle A-B-C, a triangle D-E-F, and a single bridge edge C-D joining them — 7 edges total. The true global minimum cut is exactly that one bridge edge, size 1 (confirmed below by brute force over every possible split, not just asserted). Press Step or Run to contract one uniformly random remaining edge at a time — the chosen edge turns black, its two endpoints merge and are colored to show they're now the same super-node — until two super-nodes remain. Because the choice is genuinely random, most runs won't find the bridge: watch the "cut found" number after a Reset and a fresh Run, and try it several times.

Why random contraction ever finds the minimum cut

Fix any specific minimum cut with k edges (on the demo graph, k = 1, the bridge). The contraction algorithm finds that exact cut if and only if it never happens to pick one of that cut's own k edges across all n − 2 contraction steps — picking a cut edge merges the two sides the cut is trying to keep apart, destroying it for good. Here's the key fact: if the graph's global minimum cut has weight k, then every node must have degree at least k (isolating any single node is itself some cut, so it can't be cheaper than the true minimum) — which means the total edge count is at least nk/2. A uniformly random edge is therefore one of the k cut edges with probability at most k / (nk/2) = 2/n. The same argument reapplies after each contraction (the cut's own edges are still intact, so it's still a valid cut of the shrunken graph), giving a survival probability of at least 1 − 2/(n−i) at the step where n − i super-nodes remain. Multiplying across all n − 2 steps telescopes:

P(this cut survives) ≥ ∏ (i=3..n) (i-2)/i = [1·2·3···(n-2)] / [3·4·5···n] = 2 / (n(n-1))

For the demo's n = 6, that bound is 2/30 ≈ 6.7% — low for a single run, which is exactly why the widget below always repeats the algorithm rather than trusting one pass. The bound is a guaranteed floor, not a typical value: it assumes the absolute worst case where a node's degree is exactly the cut weight everywhere, which real graphs rarely hit exactly. Measured live below, this demo graph's actual single-run success rate comes in well above 6.7%, because a triangle-bridge-triangle shape has an unusually obvious weak point.

Reference implementation

Matches the demo above one for one — same random edge choice each step, same multigraph bookkeeping, just without the per-step snapshots the demo keeps for stepping through:

function kargerMinCut(numNodes, edges) {
  // edges: [[a, b], ...] — undirected, may contain parallel pairs
  const group = Array.from({ length: numNodes }, (_, i) => i);
  let groupsLeft = numNodes;

  while (groupsLeft > 2) {
    // Rebuild the live edge list every step: only edges whose two endpoints are
    // still in *different* groups can be picked — anything else is a self-loop
    // the contraction has already collapsed and can't be chosen again.
    const live = edges.filter(([a, b]) => group[a] !== group[b]);
    const [u, v] = live[Math.floor(Math.random() * live.length)];
    const from = group[v], into = group[u];
    for (let i = 0; i < numNodes; i++) {
      if (group[i] === from) group[i] = into; // merge v's whole group into u's
    }
    groupsLeft--;
  }

  return edges.filter(([a, b]) => group[a] !== group[b]).length; // the surviving cut
}

The one subtlety with real consequences: edges must keep every parallel copy of a repeated pair, never deduplicated. Two super-nodes with three original edges between them need to be three times as likely to be the next pick as two super-nodes with one edge between them — that's exactly the weighting the survival-probability argument above depends on. See Pitfalls for what happens when that's dropped.

How many repeats are actually enough?

A single run's success probability is provably low. The fix isn't a smarter single run — it's running the whole algorithm many independent times and keeping the smallest cut found across all of them, since the true minimum can never be undercounted, only missed. Both numbers below are measured live with real Math.random(), not the demo's own trace, and will vary slightly every time this button is pressed:

Pitfalls

Deduplicating parallel edges after a contraction quietly breaks the probability guarantee. It's tempting to track "which pairs of super-nodes are still connected" as a plain set, picking uniformly among pairs instead of among edges — it still produces a valid-looking cut every time, so the bug is invisible from any single run. Measured directly: implementing that dedup and running 300,000 trials of each version against the demo's own graph, the correct multiplicity-preserving version found the true minimum cut 37.2% of the time, and the deduplicated version found it only 23.7% of the time — a real, sizable drop in success rate from one silent change, on the exact same graph, over the exact same number of trials.

One run is not the algorithm — repetition is not optional. Even on this demo's unusually favorable graph, a single run's real measured success rate (see the widget above) is well under half. Treating one contraction pass as "the answer" without repeating and keeping the best silently accepts whatever cut size that one random run happened to land on — which the histogram above shows is very often larger than the true minimum.

The graph in this demo is a friendly case, not a worst case. The 6.7% theoretical floor derived above assumes a graph where every node's degree sits right at the minimum cut weight — this demo's triangle-bridge-triangle shape has C and D at degree 3, well above the cut weight of 1, so real single-run success measures much higher than the guaranteed floor. A larger or more balanced graph — a long cycle, for instance, where every node has degree exactly equal to the global min cut of 2 — sits much closer to that floor in practice, and needs proportionally more repeats to reach the same confidence.

Complexity

Time: a single run costs O(n·m) as implemented above — n − 2 contractions, each rebuilding the live-edge list by scanning all m original edges. The standard textbook bound, O(n²) per run, comes from a different representation — a weighted adjacency matrix, picking an edge in O(n) by a cumulative-weight draw over remaining rows and merging two rows/columns in O(n) — not the plain edge-list scan this small demo uses for clarity, the same simplicity-over-asymptotics tradeoff Edmonds-Karp's own dense capacity matrix makes. Reaching a constant success probability needs O(n² log n) independent repeats (from the 2/(n(n−1)) bound above, via a standard union-bound argument), for a naive total of O(n⁴ log n). The recursive Karger-Stein variant — contract down to about n/√2 nodes, then recurse twice from there instead of running the whole thing over from scratch — reuses the same partial work across attempts and brings the total down to O(n² log³ n), without changing the core contraction step at all. Space: O(n + m) for the group array and edge list.

The deterministic alternative — n − 1 max-flow computations, one fixed source against every other node as sink, keeping the smallest — is always correct on the first try and reuses Dinic's algorithm directly; see Choosing a Network Flow Algorithm for how this entry compares against all ten of the site's other Network Flow pages side by side.