Constructive Arboricity in Almost-Linear Time for Dense Graphs

Abstract

The arboricity of a graph is the minimum number of forests needed to partition its edges. We present a randomized 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 both in expectation and with high probability, where $n$ and $m$ denote the numbers of vertices and edges. In particular, it runs in almost-linear time, $O(m^{1+o(1)})$, on dense graphs with $m=Θ(n^2)$. We also give the first known almost-linear-time algorithm that constructs a partition into at most one more forest than optimal.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.