Skip to content
Tutorials Center
My learning

Topics

Lesson 132 of 225 ยท Graphs

Karger's Algorithm and Global Minimum Cut

Find the global minimum cut of a graph with Karger's random contraction algorithm in Python: how contraction works, its success probability and how to boost it.

A cut splits the vertices of a graph into two non-empty groups. Its size is the number of edges that cross between the groups. The global minimum cut is the smallest cut over all possible splits. It tells you the weakest point of a network: the fewest links whose failure disconnects it.

In network flow you found the minimum cut that separates a given source from a given sink. The global version has no source and no sink; any split counts. You could run a flow for many pairs, but there is a much stranger and shorter method: keep merging random neighbours until only two super-vertices remain. That is Karger's algorithm, and it is one of the cleanest examples of a randomized algorithm that is allowed to be wrong.

Contraction

Contracting an edge (u, v) glues u and v into one super-vertex. Every other edge that touched u or v now touches the super-vertex. Edges that ran between u and v become self-loops and are thrown away. Parallel edges are kept, because they count toward the cut size.

flowchart LR
    subgraph before["Before"]
      A((a)) --- B((b))
      A --- C((c))
      B --- C
      C --- D((d))
    end
    subgraph after["After contracting b-c"]
      A2((a)) ---|"2 parallel"| BC(("bc"))
      BC --- D2((d))
    end
    before --> after

Contracting b and c leaves two parallel edges from a to the merged vertex.

Karger's algorithm is just a loop: while more than two vertices remain, pick a uniformly random edge and contract it. The edges left between the final two super-vertices form a cut, because every original vertex now sits on one side or the other.

Why would this find the minimum cut? Fix one minimum cut with k edges. The run returns exactly that cut as long as it never contracts one of those k edges. Contraction only ever merges vertices that the cut keeps on the same side, so a cut survives untouched until one of its own edges gets picked. A minimum cut is small, so a random edge is unlikely to be one of them.

Implementing it with union-find

We do not need to rebuild the graph after each contraction. A union-find structure tracks which original vertices have been merged, and an edge whose endpoints are already in the same group is a self-loop that we skip. Picking a random remaining edge repeatedly is equivalent to shuffling the edge list once and walking through it: self-loops are skipped, and every non-loop edge is equally likely to come next.

Python One run of random contraction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Twelve independent runs give cut sizes of 2, 4, 5 and 8, and only some runs find the true answer of 2. Every number printed is a real cut (never smaller than the minimum), so a single run gives an upper bound that is sometimes tight.

How likely is success?

Let the minimum cut have k edges. Then every vertex has degree at least k (otherwise its own edges would be a smaller cut), so the graph has at least n * k / 2 edges. When i super-vertices remain, the chance of hitting a cut edge is at most k / (i * k / 2) = 2 / i. The run succeeds if it avoids the cut at every step:

TEXT
P(success) >= (1 - 2/n) * (1 - 2/(n-1)) * ... * (1 - 2/3)
            = (n-2)/n * (n-3)/(n-1) * ... * 1/3
            = 2 / (n * (n - 1))

Most terms cancel in the product. A single run succeeds with probability at least 2 / (n(n-1)), which is about 2 / n^2. That is small, but it is a guaranteed floor. Repeat the run n^2 * ln(n) times and keep the smallest cut found. The chance that every run fails is at most (1 - 2/n^2)^(n^2 ln n) <= e^(-2 ln n) = 1/n^2, which is tiny.

Python Measuring success and repeating the run

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On this graph about 27% of single runs succeed, far above the 2.2% guarantee, because the two clusters are dense and only 2 of the 22 edges cross between them. The bound is a worst case that real graphs rarely reach. The repeated version found the true minimum, confirmed by checking all 2^(n-1) splits by brute force. The last line shows the same agreement on a small graph without any bridge-like structure: the minimum cut is 2 (vertices 2 and 5 have only two edges each, and cutting one of them off costs exactly that).

Cost and improvements

One run does a shuffle and a union-find pass: about O(E) time. With n^2 ln n repetitions the total is O(n^2 E log n), which does not beat the best deterministic methods. What matters is how simple the idea is.

Karger-Stein makes it faster with one observation: early contractions are very unlikely to destroy the cut (the risk is 2/i and i is large), while late ones are dangerous. So contract down to about n / sqrt(2) vertices, then branch into two independent recursive runs and keep the better result. This lifts the success probability to Omega(1 / log n) per call at O(n^2 log n) time, and a few repetitions finish the job.

A related fact: a graph has at most n(n-1)/2 distinct minimum cuts. Each minimum cut is returned with probability at least 2/(n(n-1)), and the events "the run returns cut X" are disjoint, so there cannot be more than n(n-1)/2 of them.

Common mistakes

  • Treating the answer as certain. A single run is a Monte Carlo result: it never reports a cut smaller than the truth, but it can report a larger one. Repeat and take the minimum.
  • Dropping parallel edges. After contraction they carry weight; the cut size counts every edge.
  • Forgetting self-loops. An edge inside a super-vertex must be skipped, or the count of groups goes wrong.
  • Running on a disconnected graph. The minimum cut is 0, and contraction can stall because no edge joins the remaining groups.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does one run of Karger's algorithm return?

    Every run ends with a real cut, so it is never smaller than the minimum, but it equals the minimum only with probability at least 2/(n(n-1)).
  2. 2. When is a fixed minimum cut destroyed during contraction?

    Contraction merges the endpoints of an edge. Only picking an edge that crosses the cut puts its two sides in the same super-vertex.
  3. 3. About how many repetitions make failure very unlikely?

    With a single-run success probability of 2/n^2, n^2 ln n independent runs all fail with probability at most 1/n^2.
  4. 4. Why are self-loops skipped?

    An edge whose endpoints are in the same super-vertex cannot cross between the final two groups.

Summary

  • A global minimum cut is the fewest edges whose removal disconnects the graph.
  • Karger's algorithm contracts random edges until two super-vertices remain; the edges between them are the answer.
  • A shuffled edge list plus union-find implements contraction in O(E) per run.
  • One run succeeds with probability at least 2/(n(n-1)); repeating n^2 ln n times makes failure at most 1/n^2.
  • Karger-Stein branches late in the process for a much better success rate.

Next: Gomory-Hu Tree, which stores every pairwise minimum cut of a graph in a single tree.