arXiv:2610.13937 · v2

Constructive Arboricity in Almost-Linear Time for Dense Graphs

首次提交 2026-10-10 01:57

版本更新 2026-11-05 02:28

雷达观测 2026-11-06 11:07

摘要

The arboricity of a graph is the minimum number of forests needed to partition its edges. We present an algorithm that computes the exact arboricity of a simple graph and constructs an optimal forest partition in $\min\{n^{2+o(1)},m^{4/3+o(1)}\}$ time, where $n$ and $m$ denote the numbers of vertices and edges. This improves the previous $O(m^{3/2}\log(n^2/m))$ bound of Gabow. In particular, it runs in almost-linear time, $m^{1+o(1)}$, on dense graphs with $m=Θ(n^2)$. We also give an algorithm that constructs a partition into at most one more forest than optimal in $m^{1+o(1)}$ time. To our knowledge, it is the first almost-linear time algorithm for this problem.