Deterministic Min-cut in Poly-logarithmic Max-flows
Jason Li, Debmalya Panigrahi · 2020
We give a deterministic (global) min-cut algorithm for weighted undirected graphs that runs in time O(m1+ε) plus polylog ( n) max-flow computations. Using the current best max-flow algorithms, this results in an overall running time of ~O(m·min(√m, n2/3)) for weighted graphs, and m4/3+o(1)for unweighted (multi)-graphs. This is the first improvement in the running time of deterministic algorithms for the min-cut problem on general (weighted/multi) graphs since the early 1990s when a running time bound of ~O(mn) was established for this problem.