Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies

Abstract

We give almost-linear-time algorithms for approximating rooted minimum cut and maximum arborescence packing in directed graphs, two problems that are dual to each other [Edm73]. More specifically, for an $n$-vertex, $m$-edge directed graph $G$ whose $s$-rooted minimum cut value is $k$, our first algorithm computes an $s$-rooted cut of size at most $O(k{\log }^{5}n)$ in $m^{1+o(1)}$ time, and our second algorithm packs $k$ $s$-rooted arborescences with $n^{o(1)}$ congestion in $m^{1+o(1)}$ time, certifying that the $s$-rooted minimum cut is at least $k/n^{o(1)}$. Our first algorithm also works for weighted graphs. Prior to our work, the fastest algorithms for computing the $s$-rooted minimum cut were exact but had super-linear running time: either $\tilde{O}(mk)$ [Gab91] or $\tilde{O}(m^{1+o(1)}\min \{\sqrt{n},n/m^{1/3}\})$ [CLN+22]. The fastest known algorithms for packing $s$-rooted arborescences had no congestion, but required $\tilde{O}(m\cdot \mathrm{poly}(k))$ time [BHKP08].