Testable algorithms for approximately counting edges and triangles in sublinear time and space
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908556870025216 |
|---|---|
| author | Eden, Talya Rubinfeld, Ronitt Vasilyan, Arsen |
| author_facet | Eden, Talya Rubinfeld, Ronitt Vasilyan, Arsen |
| contents | We consider the fundamental problems of approximately counting the numbers of edges and triangles in a graph in sublinear time. Previous algorithms for these tasks are significantly more efficient under a promise that the arboricity of the graph is bounded by some parameter $\overlineα$. However, when this promise is violated, the estimates given by these algorithms are no longer guaranteed to be correct.
For the triangle counting task, we give an algorithm that requires no promise on the input graph $G$, and computes a $(1\pm ε)$-approximation for the number of triangles $t$ in $G$ in time $O^*\left( \frac{m\cdot α(G)}{t} + \frac{m}{t^{2/3}}
\right)$, where $α(G)$ is the arboricity of the graph. The algorithm can be used on any graph $G$ (no prior knowledge the arboricity $α(G)$ is required), and the algorithm adapts its run-time on the fly based on the graph $G$.
We accomplish this by trying a sequence of candidate values $\tildeα$ for $α(G)$ and using a novel algorithm in the framework of testable algorithms. This ensures that wrong candidates $\tildeα$ cannot lead to incorrect estimates: as long as the advice is incorrect, the algorithm detects it and continues with a new candidate. Once the algorithm accepts the candidate, its output is guaranteed to be correct with high probability.
We prove that this approach preserves - up to an additive overhead - the dramatic efficiency gains obtainable when good arboricity bounds are known in advance, while ensuring robustness against misleading advice. We further complement this result with a lower bound, showing that such an overhead is unavoidable whenever the advice may be faulty.
We further demonstrate implications of our results for triangle counting in the streaming model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_20351 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Testable algorithms for approximately counting edges and triangles in sublinear time and space Eden, Talya Rubinfeld, Ronitt Vasilyan, Arsen Data Structures and Algorithms We consider the fundamental problems of approximately counting the numbers of edges and triangles in a graph in sublinear time. Previous algorithms for these tasks are significantly more efficient under a promise that the arboricity of the graph is bounded by some parameter $\overlineα$. However, when this promise is violated, the estimates given by these algorithms are no longer guaranteed to be correct. For the triangle counting task, we give an algorithm that requires no promise on the input graph $G$, and computes a $(1\pm ε)$-approximation for the number of triangles $t$ in $G$ in time $O^*\left( \frac{m\cdot α(G)}{t} + \frac{m}{t^{2/3}} \right)$, where $α(G)$ is the arboricity of the graph. The algorithm can be used on any graph $G$ (no prior knowledge the arboricity $α(G)$ is required), and the algorithm adapts its run-time on the fly based on the graph $G$. We accomplish this by trying a sequence of candidate values $\tildeα$ for $α(G)$ and using a novel algorithm in the framework of testable algorithms. This ensures that wrong candidates $\tildeα$ cannot lead to incorrect estimates: as long as the advice is incorrect, the algorithm detects it and continues with a new candidate. Once the algorithm accepts the candidate, its output is guaranteed to be correct with high probability. We prove that this approach preserves - up to an additive overhead - the dramatic efficiency gains obtainable when good arboricity bounds are known in advance, while ensuring robustness against misleading advice. We further complement this result with a lower bound, showing that such an overhead is unavoidable whenever the advice may be faulty. We further demonstrate implications of our results for triangle counting in the streaming model. |
| title | Testable algorithms for approximately counting edges and triangles in sublinear time and space |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.20351 |