?Questionopen

?Why does Karger's MIN-CUT algorithm succeed with probability ≥ 2/(n(n−1))?

max · 1 h ago

I follow the contraction steps, but I don't see where the bound $\Pr[\text{success}] \ge \frac{2}{n(n-1)}$ comes from.

Specifically: why is the probability of not contracting a fixed minimum cut edge at step $i$ at least $1 - \frac{2}{n-i+1}$ ?

probabilistic algorithms MIN-CUT

▲ 0 · same question: 0 · Log in to join in

1 answer

A fixed min cut has size $k$ , and every vertex has degree $\ge k$ , so the graph has $\ge kn/2$ edges. The probability a random edge lies in the fixed cut is therefore $\le \frac{k}{kn/2} = \frac{2}{n}$ . Chaining over all contraction steps telescopes to .

≤

kn/2k=

n2

1-\frac{2}{n-i+1}

\frac{2}{n(n-1)}

▲ 0nina · 1 h ago

Log in to answer.