Karger Contraction Success

Concept

The fundamental operation of Karger's algorithm is a form of edge contraction. The algorithm repeatedly randomly chooses an edge, and merges the two endpoints of that edge into a single supernode. All edges connecting these two nodes are removed (no self-loops). Edges to other nodes are kept, creating a multigraph.

The algorithm stops when only two supernodes remain. The edges between these two supernodes represent a cut in the original graph.

A key property is that the probability that a specific minimum cut is preserved (i.e., none of its edges are contracted) is bounded below by 2 / (n(n-1)), where n is the number of vertices. Since this probability can be small, the algorithm is typically run multiple times independently to ensure a high probability of finding a minimum cut. For R independent runs, if the success probability of one run is p, the probability of at least one success is 1 - (1 - p)^R.

Worked Example

Consider the "Heavy pairs" graph which has 4 nodes and the following edges: (0, 1) with weight 3, (2, 3) with weight 3, and (1, 2) with weight 1. The true minimum cut has a size of 1, splitting the graph into partitions {0, 1} and {2, 3}.

Let's trace one specific contraction path that preserves the minimum cut.

1. Initial State: Nodes 0, 1, 2, 3. Total edge weight is 3 + 3 + 1 = 7.
2. Step 1: Suppose we randomly select the edge (0, 1) with weight 3. The probability of choosing this edge is 3/7 ≈ 0.42857. We contract 0 and 1 into a supernode {0, 1}.
3. Intermediate State: Supernodes {0, 1}, {2}, {3}. Edges are ({0, 1}, 2) with weight 1 and (2, 3) with weight 3. Total weight is 4.
4. Step 2: Suppose we randomly select the edge (2, 3) with weight 3. The probability of choosing this edge is 3/4 = 0.75. We contract 2 and 3 into a supernode {2, 3}.
5. Final State: Supernodes {0, 1} and {2, 3}. Only the edge ({0, 1}, {2, 3}) remains, with weight 1.
6. Result: We have found a cut of size 1. The probability of this specific path is (3/7) * (3/4) = 9/28 ≈ 0.3214285714285714.

Since there is another symmetric path contracting (2, 3) first, the exact single-run success probability of finding this cut is 9/28 + 9/28 = 18/28 ≈ 0.6428571428571429.

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".

Limitations

This module enumerates all possible contraction outcomes for very small graphs (4 vertices) to allow exact calculation of probabilities. Enumerating all paths for larger graphs becomes computationally infeasible because the number of possible edge selections grows factorially.

In practice, Karger's algorithm is not used to list all outcomes, but rather to quickly find a minimum cut with high probability.

References

The mathematical details, including the proof of the probability lower bound and the deterministic implementation bounds, are available in the original paper:
Karger, D. R. (1993). Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. SODA '93: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms.
https://people.csail.mit.edu/karger/Papers/contract.pdf