Minimum-Cost k-Arborescence Packing in O(km+k⁴ n) Time

We give a deterministic, strongly polynomial algorithm running in Õ(km+k⁴n) time that finds k arc-disjoint arborescences of minimum total cost in a directed multigraph with n vertices and m arcs. This significantly improves upon the state of the art for k ≥ 2 with k=nᵒ⁽¹⁾: the prior fastest weakly polynomial and strongly polynomial algorithms take Õ(km√nlog C) and Õ(kmn) time (Gabow and Xu, 1989; Gabow, 1995), respectively. Roughly, our technique can be viewed as a way to apply a linear number of shortest augmenting paths in near-linear total time for the special case of the weighted matroid intersection problem between the k-fold graphic matroid and the indegree partition matroid. This was previously done in the unweighted case by Gabow (1995), but our approach is different. As an extension, we also obtain a deterministic Õ(km¹⁺ᵒ⁽¹⁾+k⁵n)-time algorithm for minimum-cost maximum-cardinality packing of k forests in undirected graphs. In particular, this finds k edge-disjoint spanning trees of minimum total cost, if they exist. The previous fastest algorithm takes Õ(kn²+m) time (Gabow and Westermann, 1992).