Local Flow Partitioning for Faster Edge Connectivity

Understand

We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic $O(m \log^2 n \log\log^2 n)$ time algorithm.

• This improves both on the best previously known deterministic running time of $O(m \log^{12} n)$ (Kawarabayashi and Thorup, STOC 2015) and the best previously known randomized running time of $O(m \log^{3} n)$ (Karger, J.ACM 2000) for this problem, though Karger's algorithm can be further applied to weighted graphs.
• Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian.
• Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low-conductance cuts.