Skip to content
Get started

Random contraction finds the bridge

A graph has 66 vertices: two triangles, {1,2,3}\{1,2,3\} and {4,5,6}\{4,5,6\}, joined by the single edge 33-44 (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 22 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)+
  1. The run succeeds iff the bridge is never picked. How many live edges are there at each stage?
  2. Track only the number of internal edges left in each triangle: 3, then 2, then 0.

Answer

Reveal 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

Related questions