Minimum Cut in $O(m\log^2 n)$ Time
Paweł Gawrychowski, Shay Mozes, Oren Weimann · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2019
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² n) time. This is the first improvement to Karger’s celebrated O(m log³ n) time algorithm from 1996. Our main technical contribution is a deterministic O(m log n) time algorithm that, given a spanning tree T of G, finds a minimum cut of G that 2-respects (cuts two edges of) T.