Improved Bounds for Estimating Average Degree of Graphs

Abstract

We propose a randomized parameter-oblivious algorithm that, given query access to a graph $G$ with arboricity $\alpha$, and average degree $d$, makes $\tilde{O}\left(\frac{\alpha }{{\epsilon }^{2}d}\right)$ Degree and $\tilde{O}\left(\frac{1}{{\epsilon }^2}\right)$ RandEdge queries to obtain an estimate $\hat{d}$ satisfying $\hat{d}\in (1\pm \epsilon )d$. This also yields an algorithm that uses $\tilde{O}\left(\frac{1}{{\epsilon }^2}\min (d,\frac{\alpha }{d})\right)$ Degree and RandEdge queries. This improves the ${\tilde{O}}_{\epsilon ,\log n}(\frac{1}{{\epsilon }^2}$ $\min (d,\sqrt{\frac{n}{d}}))$ query algorithm of [Beretta et al., SODA 2026] that has access to Degree, Neighbour, and RandEdge queries. We show that any algorithm that has access to Degree, Neighbour, and RandEdge queries, must make at least $\Omega \left(\min \left(d,\frac{\alpha }{d}\right)\right)$ queries, even with the knowledge of $n$ and $\alpha$. Even with Pair and FullNbr queries, an algorithm must make $\Omega \left(\min \left(d,\frac{\alpha }{d}\right)\right)$ queries for certain ranges of $\alpha$. When $n$ is unknown, any algorithm with access to all the queries discussed above must make $\Omega \left(\min \left(d,\frac{\alpha }{d}\right)\right)$ queries. We also establish that any sublinear algorithm using Degree and RandEdge queries must make at least $\Omega (\frac{1}{\epsilon })$ RandEdge queries. Furthermore, any algorithm having access to Degree, FullNbr, and RandEdge queries that makes $o(\frac{1}{{\epsilon }^2})$ RandEdge queries must make $\Omega (\frac{\alpha }{{\epsilon }^{2}d})$ Degree and FullNbr queries. This settles the query complexity of estimating average degree using Degree and FullNbr queries.

arXiv comment32 pages, 5 Figures, 3 Tables