2025/02/21 by Bishnu, Arijit, Chanda, Debarshi, Mishra, Gopinath · 4 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.15379
Given a simple, unweighted, undirected graph G=(V,E) with |V|=n and |E|=m, and parameters 0 < ε, δ<1, along with Degree, Neighbour, Edge and RandomEdge query access to G, we provide a query based randomized algorithm to generate an estimate \widehatT of the number of triangles T in G, such that \widehatT ∈ [(1-ε)T , (1+ε)T] with probability at least 1-δ. The query complexity of our algorithm is \widetildeO(m αlog(1/δ)/ε3 T), 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 RandomEdge query. Of these works, Eden et al. [SODA 2020] considers the role of arboricity. Our work considers how 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Ω(m αlog(1/δ)/ε2 T) that matches the upper bound exactly on arboricity and the parameter δ and almost on ε.