Approximating the Arboricity in Sublinear Time

We consider the problem of approximating the arboricity of a graph G = (V, E), which we denote by arb(G), in sublinear time, where the arboricity of a graph is the minimal number of forests required to cover its edge set. 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 , such that with probability 1–1/poly(n), arb(G) ≤ ≤ clog2 n-arb(G), where n = |V| and c is a constant. The expected query complexity and running time of the algorithm are O(n/arb(G)) · poly(log n), and this upper bound also holds with high probability. This bound is optimal for such an approximation up to a poly (log n) factor. For the closely related problem of finding the densest subgraph, Bhattacharya et al. (STOC, 2015) showed that there exists a factor-2 approximation algorithm that runs in time O(n) · poly (log n). In a follow up work, McGregor et al. (MFCS, 2015) improved the approximation factor to (1 + ∊) with the same complexity.