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.

Authors

• Ruoxu Cen
• Jason Li 0006
• Danupon Nanongkai
• Debmalya Panigrahi
• Thatchaphol Saranurak
• Kent Quanrud

Keywords

• Computer science
• Runtime
• Directed graphs
• Approximation algorithms
• Directed Graph
• Minimum Cut
• Estimation Algorithm
• Local Algorithm
• Flow Algorithm
• Sparse Graph
• Minimum Edge
• Edge Time
• Random Sampling
• Running Time
• Edge Weights
• Maximum Flow
• Subtree
• Minimum Weight
• Exact Algorithm
• Single Edge
• Original Graph
• Cut Set
• Unweighted Graph
• Cut Algorithm
• Directed minimum cut
• Sparsification