2022/07/06 by Addanki, Raghavendra, McGregor, Andrew, Musco, Cameron · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2207.02817
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. (ITCS '18). 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 O(ε-5log5 n ), where O(⋅) hides \textrmpoly(log log n) dependencies. This is the first non-adaptive algorithm in this setting achieving \textrmpoly(1/ε,log n) query complexity. Prior work requires Ω(log2 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 log11 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 O(ε-6 log6 n), improving on the works of Dell et al. (SODA '20) and Bhattacharya et al. (STACS '22), which require Ω(log3 n) rounds of adaptivity. Finally, as a consequence of our edge sampling algorithm, we obtain a O(nlog^ 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(n2) queries.