2026-07-29T18:42:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16940 2024-03-06T10:58:46Z ddc:004 open_access

Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries Addanki, Raghavendra McGregor, Andrew Musco, Cameron sublinear graph algorithms bipartite independent set queries edge sampling and counting graph connectivity query adaptivity We study the problem of estimating the number of edges in an n-vertex graph, accessed via the Bipartite Independent Set query model introduced by Beame et al. (TALG '20). In this model, each query returns a Boolean, indicating the existence of at least one edge between two specified sets of nodes. We present a non-adaptive algorithm that returns a (1± ε) relative error approximation to the number of edges, with query complexity Õ(ε^{-5}log⁵ n), where Õ(⋅) hides poly(log log n) dependencies. This is the first non-adaptive algorithm in this setting achieving poly(1/ε,log n) query complexity. Prior work requires Ω(log² n) rounds of adaptivity. We avoid this by taking a fundamentally different approach, inspired by work on single-pass streaming algorithms. Moreover, for constant ε, our query complexity significantly improves on the best known adaptive algorithm due to Bhattacharya et al. (STACS '22), which requires O(ε^{-2} log^{11} n) queries. Building on our edge estimation result, we give the first {non-adaptive} algorithm for outputting a nearly uniformly sampled edge with query complexity Õ(ε^{-6} log⁶ n), improving on the works of Dell et al. (SODA '20) and Bhattacharya et al. (STACS '22), which require Ω(log³ n) rounds of adaptivity. Finally, as a consequence of our edge sampling algorithm, we obtain a Õ(n log^8 n) query algorithm for connectivity, using two rounds of adaptivity. This improves on a three-round algorithm of Assadi et al. (ESA '21) and is tight; there is no non-adaptive algorithm for connectivity making o(n²) queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Raghavendra Addanki and Andrew McGregor and Cameron Musco 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.2 urn:nbn:de:0030-drops-169400 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.2 eng https://creativecommons.org/licenses/by/4.0/legalcode