A note on approximating the average degree of bounded arboricity graphs
2026-03-09 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
AI summaryⓘ
The authors revisit a previously known algorithm by Eden, Ron, and Seshadhri that estimates the average degree of a graph efficiently, especially when the graph has low arboricity (a measure of how tree-like the graph is). They clarify and simplify the description and analysis of this algorithm, removing some technical overhead like extra logarithmic factors present in the original work. Their version uses standard queries to the graph and can approximate the average degree within a small error, using fewer queries depending on the graph's arboricity and average degree. They also provide a modification for a more general query complexity bound related to the number of vertices in the graph.
average degreegraph arboricitysublinear algorithmsgraph query modelsdegree queriesneighbor queriesvertex samplingapproximation algorithms
Authors
Talya Eden, C. Seshadhri
Abstract
Estimating the average degree of graph is a classic problem in sublinear graph algorithm. Eden, Ron, and Seshadhri (ICALP 2017, SIDMA 2019) gave a simple algorithm for this problem whose running time depended on the graph arboricity, but the underlying simplicity and associated analysis were buried inside the main result. Moreover, the description there loses logarithmic factors because of parameter search. The aim of this note is to give a full presentation of this algorithm, without these losses. Consider standard access (vertex samples, degree queries, and neighbor queries) to a graph $G = (V,E)$ of arboricity at most $α$. Let $d$ denote the average degree of $G$. We describe an algorithm that gives a $(1+\varepsilon)$-approximation to $d$ degree using $O(\varepsilon^{-2}α/d)$ queries. For completeness, we modify the algorithm to get a $O(\varepsilon^{-2} \sqrt{n/d})$ query