2026-09-10T09:44:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27772 2026-09-09T12:19:38Z ddc:004 open_access

Arboricity Matters in Triangle Counting with Random Edges Bishnu, Arijit Chanda, Debarshi Mishra, Gopinath Triangle counting Sublinear algorithms Subgraph counting Given a simple, unweighted, undirected graph G = (V,E) with |V| = n and |E| = m, and parameters 0 < ε, δ < 1, along with Degree, Neighbour, Pair and RandomEdge query access to G, we provide a query-based randomized algorithm to generate an estimate T̂ of the number of triangles T in G, such that T̂ ∈ [(1-ε)T , (1+ε)T] with probability at least 1-δ. The query complexity of our algorithm is Õ(m α log(1/δ)/{ε³T}), where α is the arboricity of G. Our work can be seen as a natural progression to 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 is the first to consider how RandomEdge query can leverage the structural property of arboricity. Furthermore, continuing in the line of work of Assadi et al. [APPROX/RANDOM 2022], we also provide a lower bound of Ω̃(m α log(1/δ)/{ε²T}) that matches the upper bound exactly on arboricity, δ, and almost on ε. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arijit Bishnu and Debarshi Chanda and Gopinath Mishra 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.55 urn:nbn:de:0030-drops-277722 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.55 eng https://creativecommons.org/licenses/by/4.0/legalcode