{"ID":2833215,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.05300","arxiv_id":"2512.05300","title":"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].","short_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 $...","url_abs":"https://arxiv.org/abs/2512.05300","url_pdf":"https://arxiv.org/pdf/2512.05300v2","authors":"[\"Yonggang Jiang\",\"Yaowei Long\",\"Thatchaphol Saranurak\",\"Benyu Wang\"]","published":"2025-12-04T22:35:43Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}