Karger's Min-Cut and Fingerprinting

A cut, and a shockingly naive idea

Picture a connected undirected graph — a network of nodes joined by edges. A cut chops the vertices into two non-empty groups, and its size is the number of edges that get severed, the ones with one endpoint in each group. The min-cut is the smallest such number: the fewest edges you could delete to break the graph into two pieces. It measures how fragile the network is, and it is the undirected cousin of the s-t cut you met in network flow — except now there is no fixed source or sink, you just want the globally cheapest way to split the graph in two.

You already know one way to find it: pin one vertex as the source, try every other vertex as the sink, run max-flow for each, and take the smallest — correct, but a lot of flow computations. In 1993 David Karger proposed something that looks far too crude to work. Repeatedly pick an edge at random and contract it: glue its two endpoints into a single merged vertex, keeping all the other edges (so parallel edges can pile up between merged vertices) but throwing away any edge that now loops from the merged vertex back to itself. Keep contracting until only two vertices remain. The edges still running between those last two vertices are your guess at the min-cut.

while (number of vertices > 2):
    pick a remaining edge (u, v) uniformly at random
    contract u and v into one vertex     # keep parallel edges, drop self-loops
return the edges between the last 2 vertices

Why random gluing ever lands on the answer

Here is the one idea that makes it tick. Fix any particular minimum cut C — a specific set of k edges whose removal splits the graph. The contraction algorithm returns exactly C if and only if it never once contracts an edge that belongs to C. Why? Contracting a non-cut edge merges two vertices that sit on the same side of C, which leaves C perfectly intact as a cut of the smaller graph. But contracting a C-edge fuses the two sides together, and that cut can never be recovered. So the whole question reduces to a clean one: what is the chance we avoid all k cut edges through every contraction?

Now the counting. The key fact is that every vertex must have degree at least k — if some vertex had fewer than k edges, isolating it would itself be a cut smaller than k, contradicting that k is the minimum. With n vertices each of degree at least k, the total edge count is at least n*k/2. So when we pick the first edge uniformly at random, the probability it lands in C is at most k / (n*k/2) = 2/n, and the probability we survive — pick a safe edge — is at least 1 - 2/n. Each contraction drops the vertex count by one, and the same argument on the smaller graph gives survival probability at least 1 - 2/(n-1), then 1 - 2/(n-2), and so on down to 3 vertices.

Multiply all those survival probabilities together and a small telescoping miracle happens. The product (1 - 2/n)(1 - 2/(n-1))...(1 - 2/3) equals ((n-2)/n)((n-3)/(n-1))((n-4)/(n-2))... and almost everything cancels, collapsing to 2 / (n*(n-1)). So a single run finds any fixed min-cut with probability at least 2/(n*(n-1)), which is roughly 2/n^2. That sounds dismal — for n = 1000 it is about one in half a million — but be careful what it actually says: the probability is NOT vanishing in the bad sense, it is just polynomially small, and polynomially small is something randomness can fix.

Turning a long shot into a near-certainty

A 2/n^2 success chance per run would be useless if it were the end of the story — but it is the beginning. Run the whole contraction independently many times, each time keeping the smallest cut you have ever seen, and report the best. The runs are independent coin-flip experiments, so the probability that ALL of them miss the fixed min-cut is at most (1 - 2/n^2) raised to the number of trials. This is the same amplification logic that turned a single noisy Monte Carlo guess into a reliable answer back in the Las Vegas vs Monte Carlo guide — independence is what lets the failure probabilities multiply.

1. Use the standard squeeze: 1 - x is at most e^(-x), so a single run failing has probability at most e^(-2/n^2). Run the contraction T times independently and the chance every run fails is at most e^(-2T/n^2).
2. Choose T about (n^2 / 2) * ln n. Then the all-fail probability drops to about e^(-ln n) = 1/n, so with probability at least 1 - 1/n you have found a true min-cut — high confidence that grows with the problem size.
3. Push T a constant factor higher and the failure probability becomes 1/n^2, 1/n^3, whatever you like. You can buy any confidence you want by paying more runs; the error never reaches zero, it just shrinks below anything that matters.

Be honest about the price. One contraction run costs about O(n^2) work, and to make failure rare you need on the order of n^2 log n runs, so plain Karger lands around O(n^4 log n) — fine in theory, slow in practice, and slower than a careful max-flow approach for many graphs. The genius refinement, Karger-Stein, notices that early contractions are very safe and only the late ones (when few vertices remain) are dangerous; by recursing and only duplicating work near the risky end it reaches O(n^2 log^3 n). The headline lesson is the design pattern, not the constant: a per-run success that is merely polynomially small, amplified by independent repetition, becomes a guarantee as strong as you please.

Fingerprinting: comparing giants by a single number

Now a completely different use of randomness, and one of the most reused ideas in all of algorithm design: fingerprinting. The setup recurs everywhere — you have two enormous objects, two megabyte files, two long bit-strings, two polynomials, and you want to know whether they are equal without the expense of comparing them symbol by symbol. The trick is to hash each object down to a short random fingerprint and compare only those. If the fingerprints differ, the objects are certainly different. If they match, the objects are almost certainly equal — and you tune "almost" to be as close to certain as you like.

The cleanest example is Freivalds' algorithm for verifying matrix products. Someone hands you three n-by-n matrices A, B, C and claims A*B = C. Checking by recomputing A*B costs about O(n^3) (or O(n^2.37...) with the fanciest methods). Freivalds verifies instead in O(n^2): pick a random 0/1 vector r and test whether A*(B*r) equals C*r — three matrix-vector products, each O(n^2). If A*B truly equals C the test always passes. If A*B differs from C even in a single entry, a short calculation shows the test catches it with probability at least 1/2. That looks weak until you remember independence: run it with ten fresh random vectors and a genuinely wrong product slips through with probability at most (1/2)^10, under one in a thousand.

Fingerprints that slide: from strings to Rabin-Karp

Fingerprinting earns its keep most famously in string matching. To test whether two strings of length m are equal, treat each as a big number written in some base and reduce it modulo a random prime p — that remainder is its fingerprint, a single machine word. Two equal strings always share a fingerprint. Two different strings collide only when p happens to divide their difference, and since a number of m digits has few prime divisors, a prime chosen randomly from a large enough range collides with probability at most about m/p, which you make tiny by picking p large. The whole comparison shrinks from m symbol checks to one number comparison.

This is the engine of Rabin-Karp matching, and it leans on one more beautiful idea: the rolling hash. To find a pattern of length m inside a text of length n, you must fingerprint every length-m window of the text. Recomputing each fingerprint from scratch would cost O(m) per window and drag you back to O(n*m). But neighbouring windows overlap in all but one character, so the fingerprint can be updated in O(1): subtract the contribution of the character sliding out, multiply by the base to shift everything up a position, and add the character sliding in — all kept under the modulus. The window's fingerprint rolls along the text one cheap step at a time.

Add it up and Rabin-Karp scans the whole text in O(n + m) expected time. When a window's fingerprint matches the pattern's, that is only a probable match: a careful version then verifies the m characters directly to rule out the rare collision, which keeps it Monte Carlo in speed but Las Vegas in correctness — never wrong, only occasionally slower. Worst-case behaviour is still O(n*m) if an adversary engineers a pile of collisions, exactly the way randomized quicksort keeps an O(n^2) worst case behind its O(n log n) expected time. The randomness buys a fast expected time and a controllable error, not an ironclad worst-case guarantee — and across Karger, Freivalds, and Rabin-Karp that is the honest, repeated bargain of this whole rung.