Karger's Randomized Min-Cut Algorithm

What Counts as a Cut, and Why the Minimum Matters

A cut of an undirected graph is any partition of its vertices into two nonempty groups. The edges that have one endpoint in each group are said to cross the cut, and removing all of them disconnects the graph into those two pieces. The size of a cut is simply the number of crossing edges (or the total weight, in a weighted graph). Unlike the classic minimum s-t cut problem from network flow theory, the global minimum cut problem does not designate a source or sink in advance. It asks a broader question: across every possible way of splitting the vertices into two groups, which split has the fewest crossing edges, period? This distinction matters enormously for how the problem is solved. Max-flow min-cut style algorithms, like Ford-Fulkerson or push-relabel methods, are built around a fixed source and sink and would need to be run for every pair of vertices, or at least n minus one carefully chosen pairs, to find the true global minimum. Karger's algorithm sidesteps the need for any source or sink entirely. It treats the graph symmetrically and lets randomness explore the space of possible partitions directly. Why care about the global minimum cut at all? It shows up as a measure of network robustness: the minimum cut size tells you the fewest links that must fail, or be attacked, to split a communication network, a power grid, or a social graph into disconnected components. A small minimum cut signals a fragile bottleneck; a large one signals a well-connected, resilient structure. It also appears in clustering and image segmentation, where a small cut often corresponds to a natural boundary between two dense communities of vertices. Finding it efficiently, especially in large graphs, is genuinely useful well beyond pure theory.

The Contraction Procedure, Step by Step

Karger's algorithm operates on a multigraph, meaning it must tolerate parallel edges between the same pair of vertices, since contractions naturally create them. The procedure is deliberately minimal. First, while more than two vertices remain, pick one edge uniformly at random from all edges currently present, including any parallel copies. Second, contract that edge: merge its two endpoint vertices into a single new combined vertex. Every edge that used to touch either of the original endpoints now touches the new merged vertex instead, so those edges survive as parallel edges rather than being deleted. Third, remove any self-loops that result, meaning edges that would now connect the merged vertex to itself, since a self-loop can never be part of a cut separating two remaining super-vertices. Repeat this pick-and-contract cycle until exactly two super-vertices remain. Whatever edges still run between those final two super-vertices, all of which were originally parallel edges accumulated through the contraction process, form the algorithm's output cut. Notice something crucial: choosing an edge uniformly at random from the current edge multiset is not the same as choosing uniformly among the original vertex pairs. Vertices that have absorbed many contractions, and therefore have high degree, are more likely to have one of their edges picked next, simply because they contribute more parallel edges to the pool. This degree-weighted randomness is not an accident or a flaw; it is precisely the mechanism that makes the probability analysis work out favorably for preserving small cuts, since edges belonging to a small minimum cut make up a comparatively tiny fraction of the total edge pool at every stage, especially early on when the graph is still large and richly connected.

Why a Single Run Can Fail, and Why It Usually Does Not

Suppose the graph's true global minimum cut has exactly k crossing edges. The algorithm's single run fails to find this specific cut precisely when, at some point during the sequence of contractions, one of those k special edges gets randomly selected and contracted. Contracting a min-cut edge merges two vertices that the true minimum cut intended to keep on opposite sides, permanently destroying any chance of recovering that particular cut later in the run. So the entire question of success or failure comes down to: what is the probability that all of the contraction steps avoid all k of the minimum cut's edges? Here is the key structural fact that makes the analysis work: if the global minimum cut has size k, then every single vertex in the graph must have degree at least k. Why? Because the cut isolating just that one vertex from everything else is itself a valid cut, so its size, namely that vertex's degree, cannot be smaller than the global minimum, or k would not truly be the minimum. Since every vertex has degree at least k, a graph with n vertices must have at least nk over 2 edges in total, by the handshake relationship between degree and edge count. That means at any stage with m remaining vertices, the current graph has at least mk over 2 edges, while only k of them belong to the cut being tracked. So the chance that a uniformly random edge pick hits one of those k dangerous edges is at most k divided by mk over 2, which simplifies to 2 over m. This bound holds at every single contraction step, and multiplying the survival probabilities across all the steps from n vertices down to 2 produces the famous result that a single run succeeds with probability at least 2 divided by n times n minus 1, which is roughly 2 over n squared.

Monte Carlo Algorithms: Trading Certainty for Simplicity and Speed

Karger's algorithm is the textbook example of a Monte Carlo algorithm, a randomized algorithm that always runs in bounded time but is only guaranteed to produce the correct answer with some probability, as opposed to a Las Vegas algorithm, which always produces the correct answer but has a randomized running time. This is a fundamentally different contract than a deterministic algorithm offers. A deterministic minimum-cut algorithm, such as one built on repeated max-flow computations, will always output the exact right answer on every single run, with no exceptions. Karger's algorithm makes no such promise for any individual run; roughly 2 over n squared success probability means that on a graph with just a few dozen vertices, a lone run is actually quite likely to return a cut that is larger than the true minimum. What makes this an acceptable, even attractive, trade is that the failure events across independent repetitions are themselves independent, since each run reshuffles its own random choices from scratch. Running the whole contraction process T independent times and keeping the smallest cut found across all of them fails only if every single one of those T attempts happens to fail, and since failure probability per run is at most one minus 2 over n squared, the probability that all T runs fail simultaneously shrinks roughly like e raised to the power of negative 2T over n squared. Choosing T proportional to n squared times the logarithm of n drives the overall failure probability down below one over n, or any other target polynomially small threshold, while the total work remains polynomial in n. This is the essential Monte Carlo bargain: accept a bounded, quantifiable chance of error in exchange for an algorithm that is dramatically simpler to state, implement, and reason about than its deterministic counterparts, and then neutralize that error probability almost entirely just by repeating cheap independent trials and keeping the best result.

Running Time and Practical Refinements

Each individual contraction can be implemented efficiently using a union-find, or disjoint-set, data structure to track which original vertices have merged into which super-vertex, letting a single contraction step run in close to constant amortized time and a full run of n minus 2 contractions complete in roughly O of m time, where m is the edge count, dominated by the cost of scanning and selecting edges. Repeating the entire process order n squared log n times to achieve high-probability correctness then yields a total expected running time on the order of O of n squared m log n, which, while polynomial and therefore theoretically efficient, can be slow in practice on large graphs compared to specialized deterministic algorithms like the Stoer-Wagner minimum cut algorithm, which finds the exact answer deterministically in O of n m plus n squared log n time using a completely different phase-based vertex-merging strategy without any randomness at all. This is where a beautiful refinement, developed by David Karger together with Clifford Stein, dramatically improves matters. Their approach, sometimes called the recursive contraction algorithm, observes that the early contractions, when the graph is large, are quite safe because the survival probability 2 over m stays close to 1, while the later contractions, as the graph shrinks toward just a few vertices, are the risky ones. So instead of contracting all the way down to two vertices in one pass and then restarting from scratch, the refined algorithm contracts down to roughly n over the square root of 2 vertices, then branches into two independent recursive attempts from that safer intermediate state, taking the better of the two results. This recursive branching reduces the total running time to O of n squared log n while keeping the same high-probability correctness guarantee, illustrating how the basic Monte Carlo idea can be layered with smarter resource allocation once you understand precisely where the risk of failure is concentrated.

Frequently asked questions

Try it live

Everything above runs in your browser — open Karger's Randomized Min-Cut Algorithm and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.