Analyze Karger's Contraction Algorithm

Bound survival of a fixed minimum cut and choose an amplification count.

Problem

Prove that one run of Karger's contraction algorithm outputs a minimum cut with probability at least $2/(n(n-1))$. How many independent runs suffice for failure probability at most $\delta$?

Hint 1

Condition on a fixed minimum cut of size $\lambda$ surviving until $i$ supervertices remain.

Hint 2

Minimum degree is at least $\lambda$, so the current multigraph has at least $i\lambda/2$ edges.

Full solution

While the fixed cut survives, contraction does not reduce its size $\lambda$, and every supervertex has degree at least $\lambda$; otherwise its incident edges would form a smaller cut. Thus with $i$ supervertices there are at least $i\lambda/2$ edges. At most $\lambda$ are in the fixed cut, so the conditional probability of preserving it in the next contraction is at least $1-2/i$.

Multiplying conditional probabilities,

If the cut survives to two supervertices, the algorithm outputs it. Independent runs all fail with probability at most $(1-p)^r\le e^{-pr}$. Therefore it suffices to choose

Checkpoint

Parallel edges encode multiplicity and must remain. Only self-loops are deleted after contraction.

Provenance note

Independently phrased standard analysis of Karger's algorithm. Student submissions are not authoritative.

Common mistakes

• Skipping a direction of correctness or an input-format edge case.
• Measuring resources against a numeric value rather than encoded input length.
• Treating an informal intuition as a proof of the stated bound.

Sources and verification

• Arora-Barak draft, randomized-algorithms discussion
• Corpus coverage note: No direct merged-summary or 2026 transcript coverage.
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Open in the visualization gallery: Karger contraction