Karger's Min-Cut Algorithm ·multigraph G(V,E) Karger's Algorithm: whileV>2 do: pick random e∈E; contract(e); return remaining edges; edges returned
edges returned • multigraph G(V, E) Karger’s Min-Cut Algorithm Karger’s Algorithm: while do: pick random ; contract ; return remaining edges; |V| > 2 e ∈ E (e)
Karger's Algorithm: Theorem(Karger 1993). while VI>2 do: 2 Pr a min-cut is returned n(n-1) pick random e∈E, contract(e); repeat independently for n(n -1)Inn times return remaining edges; and return the smallest cut Pr[fail to output a min-cut at last n(n-DInn Pr[fail to output a min-cut in one trial s(） () 1 n Succeed with high probability (w.h.p.)!
repeat independently for times and return the smallest cut 1 2 n(n − 1)ln n Pr[ fail to output a min-cut at last ] = Pr[ fail to output a min-cut in one trial ] n(n − 1) 2 ln n ≤ (1 − 2 n(n − 1)) n(n − 1) 2 ln n < ( 1 e ) ln n = 1 n Theorem (Karger 1993). Pr [ a min-cut is returned ] ≥ 2 n(n − 1) Succeed with high probability (w.h.p.)! Karger’s Algorithm: while do: pick random ; contract ; return remaining edges; |V| > 2 e ∈ E (e)