Today I read a paper titled “Minimum Cuts in Near-Linear Time”
The abstract is:
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs.
We use a “semi-duality” between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques.
We give a randomized algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log^3 n) time.
We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O(n^2 log n) time.
This variant has an optimal RNC parallelization.
Both variants improve on the previous best time bound of O(n^2 log^3 n).
Other applications of the tree-packing approach are new, nearly tight bounds on the number of near minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.