Minimum Cuts in Directed Graphs via Partial Sparsification

We give an algorithm to find a minimum cut in an edge-weighted directed graph with
$n$
vertices and
$m$
edges in
$\tilde{O}(n\cdot\max\{m^{2/3},\ n\})$
time. This improves on the 30 year old bound of
$\tilde{O}(nm)$
obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain
$\tilde{O}(n^{2}/\epsilon^{2})$
-time
$(1+{\epsilon})$
-approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed
$\epsilon$
. Before our work, no (1 +
$\epsilon)$
-approximation algorithm better than the exact runtime of
$\tilde{O}(nm)$
is known for either problem. Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to
$\tilde{O}(\min\{{n}/m^{1/3}, \sqrt{n}\}){-}$
calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.