Home▸Algorithms & AI▸Karger's Randomized Min-Cut Algorithm

✂️ Karger's Randomized Min-Cut Algorithm

Explore how Karger's algorithm finds the global minimum cut of a graph by repeatedly contracting random edges until two super-vertices remain, and see why repeating this simple random process drives the chance of error down to almost nothing.

Algorithms & AI3DModerate60 FPS

The simulator shows a graph shrinking edge by edge as Karger's algorithm randomly selects and contracts edges, visually merging vertices into growing super-vertices while parallel edges accumulate between them, until only two super-vertices and their connecting edges remain as the candidate minimum cut. Running many independent trials side by side reveals how cut sizes vary between attempts and how the best-so-far result converges toward the true global minimum cut as more trials accumulate.

🔬 What It Demonstrates

🎮 How to Use

Load or generate a graph, then step through contractions one at a time to watch a single random edge get selected and its endpoints merge, or let the run play automatically to completion. Compare the resulting cut size against the graph's known true minimum cut. Switch to repeated-trial mode to launch many independent runs in sequence, track the smallest cut size found so far after each trial, and watch the empirical failure rate shrink as the trial count grows, directly illustrating the Monte Carlo repetition argument.

💡 Did You Know?

For a graph shaped like a simple cycle of n vertices, where the true minimum cut has size exactly 2, a single run of Karger's algorithm succeeds in finding that minimum cut with probability exactly 2 over n, meaning on a 100-vertex cycle a lone attempt only succeeds about 2 percent of the time, yet a few hundred independent repetitions push the overall success probability above 99 percent.

⚙ Under the hood

graph theoryrandomized algorithmsmin cutmonte carlocomputer sciencecombinatoricsnetwork flowalgorithms

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install