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)$ time. This is the first improvement to Karger’s celebrated $O(m{\log }^{3}n)$ time algorithm from 1996. Our main technical contribution is a deterministic $O(m \log n)$timealgorithmthat,givenaspanningtree$T$of$G$, finds a minimum cut of $G$ that 2-respects (cuts two edges of) $T$.