Minimum Cuts in Directed Graphs via $\sqrt{n}$ Max-Flows

Abstract

We give an algorithm to find a mincut in an $n$-vertex, $m$-edge weighted directed graph using $\tilde{O}(\sqrt{n})$ calls to any maxflow subroutine. Using state of the art maxflow algorithms, this yields a directed mincut algorithm that runs in $\tilde{O}(m\sqrt{n}+n^2)$ time. This improves on the 30 year old bound of $\tilde{O}(mn)$ obtained by Hao and Orlin for this problem.