Minimum Cut in \(O(m\log ^2 n)\) Time

We give a randomized algorithm that finds a minimum cut in an undirected weighted m-edge n-vertex graph G with high probability in \(O(m \log ^2 n)\) $O(m{log}^{2}n)$ time. This is the first improvement to Karger’s celebrated \(O(m \log ^3 n)\) $O(m{log}^{3}n)$ time algorithm from 1996. Our main technical contribution is a deterministic \(O(m \log n)\) $O(mlogn)$ time algorithm that, given a spanning tree T of G, finds a minimum cut of G that 2-respects (cuts two edges of) T.