MinCut multigraph G(V,E)) Theorem (Karger 1993): while IV>2 do Pra min-cut is returned) 2 choose a uniform e∈E; contract(e); repeat independently return remaining edges; for n(n-1)/2 times and return the smallest cut Prfail to finally return a min-cut (Pr[fail to find a min-cut in a runningl)n(n-1)/2 n(n-1)/2 1 e
MinCut ( multigraph G(V,E) ) while |V|>2 do • choose a uniform e ∈E ; contract(e); return remaining edges; Pr[a min-cut is returned] 2 n(n1) Theorem (Karger 1993): repeat independently for n(n-1)/2 times and return the smallest cut = (Pr[fail to find a min-cut in a running])n(n1)/2 1 2 n(n 1)n(n1)/2 < 1 e Pr[fail to finally return a min-cut]
MinCut（multigraph G(V,E)） suppose e1,e2,...,en-2 while IV>2 do are contracted edges choose a uniform e∈E; initially:G1=G contract(e); i-th round: return remaining edges; Gi=contract(Gi-1,ei-1) Cian nte-cn ei-1C C is a min-cut in Gi C:a min-cut of G Pr[C is returned]=Pr[e1,e2,...,en-2] n-2 chain rule:=Pr[e年C|e1,e2,,ei-1年C i=1
MinCut ( multigraph G(V,E) ) while |V|>2 do • choose a uniform e ∈E ; contract(e); return remaining edges; = n Y2 i=1 Pr[ei 62 C | e1, e2,...,ei1 62 C] suppose e1, e2,...,en2 are contracted edges initially: G1 = G i-th round: C: a min-cut of G Pr[C is returned] = Pr[e1, e2,...,en2 62 C] chain rule: Gi = contract(Gi1, ei1) C is a min-cut in Gi1 o C is a min-cut in Gi ei1 62 C
suppose e1,e2,...,en-2 are contracted edges initially:G1-G i-th round:Gi=contract(Gi-1,ei-1) C is a min-cut in Gi-1 e:-1C } C is a min-cut in Gi C:a min-cut of G m-2 Pr[C is returned]=Prlee1,e2,...,e] i=1 Q C is a min-cut in Gi C is a min-cut in G(V,E) >IE≥CIV川 Proof.degree of G≥lCl
= n Y2 i=1 Pr[ei 62 C | e1, e2,...,ei1 62 C] suppose e1, e2,...,en2 are contracted edges initially: G1 = G i-th round: Pr[C is returned] C is a min-cut in Gi C is a min-cut in G(V,E) |E| 1 2 |C||V | C: a min-cut of G Proof: degree of G ≥ |C| Gi = contract(Gi1, ei1) C is a min-cut in Gi1 o C is a min-cut in Gi ei1 62 C