Faster algorithms for packing forests in graphs and related problems

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\delta m\log n)\), where \(n,m\) are the number of vertices and edges in \(G\) respectively, and \(\delta = \max\{1, k - k_G\}\), where \(k_G\) is the edge connectivity of the graph. Using our solution to this problem, we improve complexities for two existing applications: