Random contraction finds the bridge
A graph has vertices: two triangles, and , joined by the single edge - (7 edges in all). Its unique minimum cut is that bridge. Karger's algorithm repeatedly picks an edge uniformly at random among the edges still joining different super-vertices, merges its two endpoints (deleting any edges that become self-loops and keeping parallel edges), and stops when super-vertices remain; it outputs the edges between them. What is the probability that one run outputs the minimum cut? Give a decimal to four places.
Show hints (2)+
- The run succeeds iff the bridge is never picked. How many live edges are there at each stage?
- Track only the number of internal edges left in each triangle: 3, then 2, then 0.
Answer
Reveal answer →Final answer
0.3714 (± 0.001)
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading, Systematic & Data-Driven Trading