2025/12/04 by Yonggang Jiang, Jiang, Yonggang, Yaowei Long +5
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2512.05300
openalex publication_date 2025/12/04 · openalex created_date 2025/12/09 · openalex updated_date 2026/07/31
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(klog5 n) in m1+o(1) time, and our second algorithm packs k s-rooted arborescences with no(1) congestion in m1+o(1) time, certifying that the s-rooted minimum cut is at least k / no(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 O(mk) [Gab91] or O(m1+o(1)min\√(n),n/m1/3\) [CLN+22]. The fastest known algorithms for packing s-rooted arborescences had no congestion, but required O(m ⋅ poly(k)) time [BHKP08].