{"ID":2892255,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.15598","arxiv_id":"2507.15598","title":"Fast Algorithms for Graph Arboricity and Related Problems","abstract":"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 $\\tilde{O}(nm)$ for weighted graphs and $\\tilde{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)}$. 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. The cut hierarchy yields the ideal edge loads (Thorup 2001) in a fractional spanning tree packing of the graph which, we show, also corresponds to a max-entropy solution in the spanning tree polytope. For the cut hierarchy problem, the previous best bound was $\\tilde{O}(n^2 m)$ for weighted graphs and $\\tilde{O}(n m^{3/2})$ for unweighted graphs.","short_abstract":"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 $\\tilde{O}(nm)$ for weighted graphs and $\\tilde{O}(m^{3/2}) $ for unweighted gr...","url_abs":"https://arxiv.org/abs/2507.15598","url_pdf":"https://arxiv.org/pdf/2507.15598v1","authors":"[\"Ruoxu Cen\",\"Henry Fleischmann\",\"George Z. Li\",\"Jason Li\",\"Debmalya Panigrahi\"]","published":"2025-07-21T13:19:11Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}