Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.15379 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915164980248576 |
|---|---|
| author | Bishnu, Arijit Chanda, Debarshi Mishra, Gopinath |
| author_facet | Bishnu, Arijit Chanda, Debarshi Mishra, Gopinath |
| contents | Given a simple, unweighted, undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=m$, and parameters $0 < \varepsilon, δ<1$, along with \texttt{Degree}, \texttt{Neighbour}, \texttt{Edge} and \texttt{RandomEdge} query access to $G$, we provide a query based randomized algorithm to generate an estimate $\widehat{T}$ of the number of triangles $T$ in $G$, such that $\widehat{T} \in [(1-\varepsilon)T , (1+\varepsilon)T]$ with probability at least $1-δ$. The query complexity of our algorithm is $\widetilde{O}\left({m α\log(1/δ)}/{\varepsilon^3 T}\right)$, where $α$ is the arboricity of $G$. Our work can be seen as a continuation in the line of recent works [Eden et al., SIAM J Comp., 2017; Assadi et al., ITCS 2019; Eden et al. SODA 2020] that considered subgraph or triangle counting with or without the use of \texttt{RandomEdge} query. Of these works, Eden et al. [SODA 2020] considers the role of arboricity. Our work considers how \texttt{RandomEdge} query can leverage the notion of arboricity. Furthermore, continuing in the line of work of Assadi et al. [APPROX/RANDOM 2022], we also provide a lower bound of $\widetildeΩ\left({m α\log(1/δ)}/{\varepsilon^2 T}\right)$ that matches the upper bound exactly on arboricity and the parameter $δ$ and almost on $\varepsilon$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_15379 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries Bishnu, Arijit Chanda, Debarshi Mishra, Gopinath Data Structures and Algorithms Given a simple, unweighted, undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=m$, and parameters $0 < \varepsilon, δ<1$, along with \texttt{Degree}, \texttt{Neighbour}, \texttt{Edge} and \texttt{RandomEdge} query access to $G$, we provide a query based randomized algorithm to generate an estimate $\widehat{T}$ of the number of triangles $T$ in $G$, such that $\widehat{T} \in [(1-\varepsilon)T , (1+\varepsilon)T]$ with probability at least $1-δ$. The query complexity of our algorithm is $\widetilde{O}\left({m α\log(1/δ)}/{\varepsilon^3 T}\right)$, where $α$ is the arboricity of $G$. Our work can be seen as a continuation in the line of recent works [Eden et al., SIAM J Comp., 2017; Assadi et al., ITCS 2019; Eden et al. SODA 2020] that considered subgraph or triangle counting with or without the use of \texttt{RandomEdge} query. Of these works, Eden et al. [SODA 2020] considers the role of arboricity. Our work considers how \texttt{RandomEdge} query can leverage the notion of arboricity. Furthermore, continuing in the line of work of Assadi et al. [APPROX/RANDOM 2022], we also provide a lower bound of $\widetildeΩ\left({m α\log(1/δ)}/{\varepsilon^2 T}\right)$ that matches the upper bound exactly on arboricity and the parameter $δ$ and almost on $\varepsilon$. |
| title | Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.15379 |