Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries

Abstract

Given a simple, unweighted, undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=m$, and parameters $0<\epsilon ,\hat{I}´<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 $\hat{T}$ of the number of triangles $T$ in $G$, such that $\hat{T}\in [(1-\epsilon )T,(1+\epsilon )T]$ with probability at least $1-\hat{I}´$. The query complexity of our algorithm is $\tilde{O}\left(m\hat{I}\pm \log (1/\hat{I}´)/{\epsilon }^{3}T\right)$, where $\hat{I}\pm$ 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 $\tilde{\hat{I}}\text{c◯}\left(m\hat{I}\pm \log (1/\hat{I}´)/{\epsilon }^{2}T\right)$ that matches the upper bound exactly on arboricity and the parameter $\hat{I}´$ and almost on $\epsilon$.

21 pages