Minimum Cuts in Near-Linear Time

MIT

Proof Outline

lGraph has O(n2) (capacitated) edges

lSo O(n2) work to contract, then two subproblems of size n/2½

»T(n) = 2 T(n/2½) + O(n2) = O(n2 log n)

lAlgorithm fails if both iterations fail

»Iteration succeeds if contractions and recursion succeed

»P(n)=1 - [1 - ½ P(n/2½)]2 = W (1 / log n)