Pick a uniformly random edge, merge its endpoints, drop the loops, repeat until two supernodes remain, and report the edges between them. On the lab's opening graph that returns a minimum cut with probability 19/35, which is exact and is not a sample; the proved bound is 2/(n(n − 1)) = 1/15; and 53 of the first 120 seeds returned something bigger. All three numbers belong on the page and only one of them is a guarantee.
Core ideas
The hard idea is why a random edge is likely to miss a small cut. The other two are what the bound is about and what the algorithm is about, which are not the same event.
Merging the endpoints of an edge produces a multigraph whose cuts are exactly the cuts of the original that keep those two vertices together. So every cut of the contracted graph is a cut of the original with the same size, and the minimum can only rise. A particular minimum cut survives as long as no edge crossing it is ever contracted — which is the only event the analysis has to track.
If the minimum cut has k edges then every vertex has degree at least k, so a graph on n vertices has at least nk/2 edges. A uniformly random edge therefore crosses a given minimum cut with probability at most k/(nk/2) = 2/n. Parallel edges are counted separately and that is the whole point: a pair of supernodes joined by many edges is likely to be merged, and merging them is harmless.
kargerExact answers “what is the probability this named cut survives?” The algorithm succeeds if it returns any minimum cut, and the lab's opening graph has three. Their probabilities are 13/70, 6/35 and 13/70, and the success probability is their sum, 19/35. Reporting the first of those as the success probability would understate it by a factor of nearly three, silently.
The material
The algorithm, the bound, the exact probability the lab computes instead, and the seeds where it did not work.
To contract an edge uv of a multigraph, replace u and v by a single supernode, redirect every other edge at u or v to it, and delete the edges that have become loops. Parallel edges are kept. Karger's algorithm repeatedly contracts a uniformly random edge until two supernodes remain, and returns the set of edges between them, which is a cut of the original graph.
The algorithm always returns a cut — the two supernodes are a bipartition of the vertices, and the surviving edges are exactly the edges crossing it. What it does not always return is a minimum cut, and that is the only thing that can go wrong. This is a Monte Carlo algorithm: the running time is fixed and the answer is sometimes wrong.
Fix a minimum cut C of a connected graph on n vertices. Karger's algorithm returns C with probability at least 2/(n(n − 1)).
Let k = |C|. Every vertex has degree at least k, or else the edges at a vertex of smaller degree would be a smaller cut, so the number of edges is at least nk/2. A uniformly random edge is one of the k in C with probability at most k/(nk/2) = 2/n, so the first contraction misses C with probability at least 1 − 2/n.
If C was missed, the contracted graph has n − 1 vertices and C is still a cut of it, still of size k, and still minimum — contraction cannot create a smaller cut. So the same bound applies with n − 1 in place of n, and inductively the probability that all n − 2 contractions miss C is at least the product of 1 − 2/i for i from n down to 3.
That product is ((n−2)/n)·((n−3)/(n−1))·…·(1/3), which telescopes to 2/(n(n − 1)). And if no edge of C was ever contracted, then every supernode lies wholly on one side of C, so the two surviving supernodes are exactly the two sides and the algorithm returns C.
□
At n = 6 the bound reads 2/30 = 1/15, about 0.067. That is a guarantee for every graph on six vertices and every minimum cut in it, and it is very far from what happens on any particular graph — which is what the rest of this page is about.
The panel does not sample and it does not quote the bound as the answer. For a named cut it computes the exact probability by recursion over contraction states: a state is the current partition of the vertices into supernodes, and the probability of success from a state is the sum over pairs of supernodes that do not straddle the cut of multiplicity/m times the probability of success from the merged state. Different contraction orders reach the same state, so the recursion is memoised and the whole computation is a few dozen states rather than |E|! edge orders.
Then it enumerates every bipartition to find all the minimum cuts, and adds their probabilities. That second step is not optional: the algorithm succeeds if it returns any of them, and on graphs with symmetry there are several.
The opening graph is 1-2, 1-3, 2-3, 4-5, 4-6, 5-6, 1-4, 2-5: six vertices, eight edges. Exhaustive search over all 31 bipartitions finds a minimum cut of 2 edges, and three cuts achieve it — isolating vertex 3, isolating vertex 6, and splitting the two triangles apart. Their exact probabilities are 13/70, 13/70 and 6/35, and the probability of returning one of the three is 19/35 ≈ 0.5429. Every one of them clears the bound 1/15.
Notice that the cut the graph was built to illustrate — the pair of joining edges — is the least likely of the three, at 6/35 against 13/70. The two cuts that isolate a single vertex are easier to find, because each is protected by only two edges out of eight rather than by two edges that the contraction of a triangle keeps threatening.
Over seeds 1 to 120 the algorithm returned a minimum cut 67 times: a rate of 67/120 ≈ 0.5583, against an exact probability of 19/35 ≈ 0.5429. The measurement is above the truth here and will be below it at another slider position, and it is a measurement either way. Move the seed count and watch it wander around a number that does not move.
Fifty-three of those 120 seeds failed, and the panel names them rather than reporting a rate and stopping. Seed 5 is the first: it returned a cut of 3 edges rather than 2. That is what with high probability means, and it is the reason the phrase is on the page in those words. A guarantee whose failures you have never seen is one you will eventually quote as though it were an always claim.
For contrast, switch the graph to a four-cycle. It has six minimum cuts, each of exactly two edges, each with probability exactly 1/6 — which is exactly the bound 2/(n(n − 1)) at n = 4 — and they sum to 1. The algorithm never fails on that graph, and 120 of 120 seeds succeeded. A graph where the bound is tight for every cut and the algorithm is nevertheless certain to succeed is worth a minute's thought: the bound is per cut, and there are six of them.
Interactive
The success probability is a recursion over contraction states, exact; the measured rate over seeds is not it, and repetition is what makes either of them useful
Method
Separate the event the bound covers from the event the algorithm is judged on.
The panel enumerates every bipartition. If there are three minimum cuts then success is a union of three events and the success probability is their sum; quoting one cut's probability as the algorithm's is the commonest error here, and it always understates.
1/15 at six vertices against an actual 19/35: the bound is out by a factor of eight on this graph. It is not wrong. It is a statement about the worst graph on six vertices, and this one is not that graph.
The panel lists the seeds that returned a bigger cut and says what they returned instead. Do that before writing down the success rate; a probabilistic guarantee is not understood until its failure mode has been seen once.
Change the seed slider. The rate moves, the exact probability does not, and the distance between them at any slider position is a sample's noise rather than information about the algorithm.
1-2, 1-3, 2-3, 4-5, 4-6, 5-6, 1-4, 2-5. Two triangles, {1, 2, 3} and {4, 5, 6}, joined by 1-4 and 2-5. Exhaustive search over the 31 bipartitions, then the exact probability of each minimum cut.
13/70 + 6/35 + 13/70: put the middle term over 70 as 12/70 and the sum is 38/70 = 19/35. Doing that addition by hand once is worth more than reading the total, because it is the step that distinguishes the algorithm's success event from any one cut's survival.
The bound of 1/15 is below every one of the three per-cut probabilities, which is what it means for the bound to hold. It is also about eight times below the algorithm's actual success probability, and the gap is not a defect in the proof — the proof has to cover the worst graph on six vertices, and no graph is the worst case for every n at once.
For a faded rehearsal, switch to the graph with a parallel pair and predict the number of minimum cuts before reading it. The supplied first move is this: two edges written between the same pair of vertices make that pair twice as likely to be contracted, and contracting them is harmless, so parallel edges help. Say what the minimum cut size is, how many cuts achieve it, and whether the success probability should be above or below 19/35 — then check all three.
You should be able to run one contraction by hand, state and prove 2/(n(n − 1)) from the minimum-degree argument, explain why the success probability is the sum over all minimum cuts, and produce a run where the algorithm failed.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.