2024/09/30 by Arkhipov, Pavel, Kolmogorov, Vladimir
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2409.20314
We consider several problems related to packing forests in graphs. The first one is to find k edge-disjoint forests in a directed graph G of maximal size such that the indegree of each vertex in these forests is at most k. We describe a min-max characterization for this problem and show that it can be solved in almost linear time for fixed k, extending the algorithm of [Gabow, 1995]. Specifically, the complexity is O(k δm log n), where n, m are the number of vertices and edges in G respectively, and δ= max\1, k - kG\, where kG is the edge connectivity of the graph. Using our solution to this problem, we improve complexities for two existing applications: (1) k-forest problem: find k forests in an undirected graph G maximizing the number of edges in their union. We show how to solve this problem in O(k3 min\kn, m\ log2 n + k ⋅\rm MAXFLOW(m, m) log n) time, breaking the Ok(n3/2) complexity barrier of previously known approaches. (2) Directed edge-connectivity augmentation problem: find a smallest set of directed edges whose addition to the given directed graph makes it strongly k-connected. We improve the deterministic complexity for this problem from O(k δ(m+δn)log n) [Gabow, STOC 1994] to O(k δm log n). A similar approach with the same complexity also works for the undirected version of the problem.