Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.03650 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912688968302592 |
|---|---|
| author | Chanda, Debarshi |
| author_facet | Chanda, Debarshi |
| contents | We propose a randomized algorithm with query access that given a graph $G$ with arboricity $α$, and average degree $d$, makes $\widetilde{O}\left(\fracα{\varepsilon^2d}\right)$ \texttt{Degree} and $\widetilde{O}\left(\frac{1}{\varepsilon^2}\right)$ \texttt{Random Edge} queries to obtain an estimate $\widehat{d}$ satisfying $\widehat{d} \in (1\pm\varepsilon)d$. This improves the $\widetilde{O}_{\varepsilon,\log n}\left(\sqrt{\frac{n}{d}}\right)$ query algorithm of [Beretta et al., SODA 2026] that has access to \texttt{Degree}, \texttt{Neighbour}, and \texttt{Random Edge} queries. Our algorithm does not require any graph parameter as input, not even the size of the vertex set, and attains both simplicity and practicality through a new estimation technique. We complement our upper bounds with a lower bound that shows for all valid $n,d$, and $α$, any algorithm that has access to \texttt{Degree}, \texttt{Neighbour}, and \texttt{Random Edge} queries, must make at least $Ω\left(\min\left(d,\fracα{d}\right)\right)$ queries to obtain a $(1\pm\varepsilon)$-multiplicative estimate of $d$, even with the knowledge of $n$ and $α$. We also show that even with \texttt{Pair} and \texttt{FullNbr} queries, an algorithm must make $Ω\left(\min\left(d,\fracα{d}\right)\right)$ queries to obtain a $(1\pm\varepsilon)$-multiplicative estimate of $d$. Our work addresses both the questions raised by the work of [Beretta et al., SODA 2026]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03650 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size Chanda, Debarshi Data Structures and Algorithms We propose a randomized algorithm with query access that given a graph $G$ with arboricity $α$, and average degree $d$, makes $\widetilde{O}\left(\fracα{\varepsilon^2d}\right)$ \texttt{Degree} and $\widetilde{O}\left(\frac{1}{\varepsilon^2}\right)$ \texttt{Random Edge} queries to obtain an estimate $\widehat{d}$ satisfying $\widehat{d} \in (1\pm\varepsilon)d$. This improves the $\widetilde{O}_{\varepsilon,\log n}\left(\sqrt{\frac{n}{d}}\right)$ query algorithm of [Beretta et al., SODA 2026] that has access to \texttt{Degree}, \texttt{Neighbour}, and \texttt{Random Edge} queries. Our algorithm does not require any graph parameter as input, not even the size of the vertex set, and attains both simplicity and practicality through a new estimation technique. We complement our upper bounds with a lower bound that shows for all valid $n,d$, and $α$, any algorithm that has access to \texttt{Degree}, \texttt{Neighbour}, and \texttt{Random Edge} queries, must make at least $Ω\left(\min\left(d,\fracα{d}\right)\right)$ queries to obtain a $(1\pm\varepsilon)$-multiplicative estimate of $d$, even with the knowledge of $n$ and $α$. We also show that even with \texttt{Pair} and \texttt{FullNbr} queries, an algorithm must make $Ω\left(\min\left(d,\fracα{d}\right)\right)$ queries to obtain a $(1\pm\varepsilon)$-multiplicative estimate of $d$. Our work addresses both the questions raised by the work of [Beretta et al., SODA 2026]. |
| title | Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.03650 |