Minimum Cuts in Near-Linear Time

MIT

Strength Lemma

lLemma: å 1/ce £ n

»Consider connected component C of G

»Suppose C has min-cut k

»Then every edge e in C has ce ³ k

»So k edges crossing C’s min-cut have

å 1/ce £ å 1/k £ k (1/k ) = 1

»Delete these edges (“cost” 1)

»Repeat n - 1 times: no more edges!