Approximating the Arboricity in Sublinear Time

Abstract

We consider the problem of approximating the arboricity of a graph $G=(V,E)$, which we denote by $\mathsf{arb}(G)$, in sublinear time, where the arboricity of a graph is the minimal number of forests required to cover its edges. An algorithm for this problem may perform degree and neighbor queries, and is allowed a small error probability. We design an algorithm that outputs an estimate $\hat{\alpha }$, such that with probability $1-1/\text{poly}(n)$, $\mathsf{arb}(G)/c{\log }^{2}n\le \hat{\alpha }\le \mathsf{arb}(G)$, where $n=|V|$ and $c$ is a constant. The expected query complexity and running time of the algorithm are $O(n/\mathsf{arb}(G))\cdot \text{poly}(\log n)$, and this upper bound also holds with high probability. %($\tilde{O}(\cdot )$ is used to suppress $\text{poly}(\log n)$ dependencies). This bound is optimal for such an approximation up to a $\text{poly}(\log n)$ factor.