Karger Contraction Success

Count the chance that random edge contractions preserve a minimum cut. Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph.

Experiment

In the Interactive module, you can trace deterministically ordered Karger edge contractions.

1. Select the "Graph" to analyze, for example "Heavy pairs".
2. Observe the "True minimum cut" calculated precisely.
3. Change the "Outcome rank" to view different deterministic contraction paths, observing how the "Selected contraction cut" and "Selected partition" vary.
4. Note the exact "Selected path probability" for each path. Paths discovering the minimum cut contribute to the overall single-run success.
5. Adjust the "Independent runs" control to observe how multiple iterations exponentially reduce the probability of failure, increasing the "Independent-run success" well beyond the theoretical "Single-run lower bound".