# Constructive Arboricity in Almost-Linear Time for Dense Graphs

Preprint · Iman Gholami, Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani, AmirMohammad Shahrezaei

- Archive id: arxiv:2610.13937
- Published: 2026-10-09
- arXiv: https://arxiv.org/abs/2610.13937
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.13937
- PDF: https://arxiv.org/pdf/2610.13937
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.