Fast Algorithms for Graph Arboricity and Related Problems

We give an algorithm for finding the arboricity of a weighted, undirected graph, defined as the minimum number of spanning forests that cover all edges of the graph, in \sqrt{n} m^{1+o(1)} time. This improves on the previous best bound of O(nm) for weighted graphs and O(m^{3/2}) for unweighted graphs (Gabow 1995) for this problem. The running time of our algorithm is dominated by a logarithmic number of calls to a directed global minimum cut subroutine—if the running time of the latter problem improves to m^{1+o(1)} (thereby matching the running time of maximum flow), the running time of our arboricity algorithm would improve further to m^{1+o(1)}.

As an application, we also give a new algorithm for computing the entire cut hierarchy—laminar multiway cuts with minimum cut ratio in recursively defined induced subgraphs—in m n^{1+o(1)} time. For the cut hierarchy problem, the previous best bound was O(n^2 m) for weighted graphs and O(n m^{3/2}) for unweighted graphs.

This is joint work with Ruoxu Cen, Henry Fleischmann, Jason Li, and Debmalya Panigrahi.