论文标题
非自适应边缘计数和通过双分部分独立集查询进行抽样
Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries
论文作者
论文摘要
我们研究了通过Beame等人引入的双方独立集合模型访问的$ n $ vertex图中边缘数量的问题。 （ITCS '18）。在此模型中，每个查询返回一个布尔值，表明两个指定的节点集之间至少存在一个边缘。 We present a non-adaptive algorithm that returns a $(1\pm ε)$ relative error approximation to the number of edges, with query complexity $\tilde O(ε^{-5}\log^{5} n )$, where $\tilde O(\cdot)$ hides $\textrm{poly}(\log \log n)$ dependencies.这是在此设置中实现$ \ textrm {poly}（1/ε，\ log n）$查询复杂性的第一个非自适应算法。先前的工作需要$ω（\ log^2 n）$圆形自适应。我们通过采用根本不同的方法来避免这种情况，这是受单频道流算法的工作的启发。此外，对于常数$ε$，由于Bhattacharya等人，我们的查询复杂性在最著名的自适应算法上显着改善。 （stacs '22），它需要$ o（ε^{ - 2} \ log^{11} n）$ queries。在我们的边缘估计结果的基础上，我们提供了第一个非自适应算法，用于输出几乎均匀的采样边缘，并具有查询复杂性$ \ tilde o（ε^{ - 6} \ log^{6} n）$，从而改善了Dell等人的作品。 （苏打'20）和Bhattacharya等。 （STACS '22），需要$ω（\ log^3 n）$自适应。最后，由于我们的边缘采样算法，我们使用两轮适应性获得了连接性的$ \ tilde o（n \ log^ 8 n）$查询算法。这改善了Assadi等人的三轮算法。 （ESA '21）并且很紧；没有用于连通性的非自适应算法，使$ O（n^2）$查询。
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\pm ε)$ relative error approximation to the number of edges, with query complexity $\tilde O(ε^{-5}\log^{5} n )$, where $\tilde O(\cdot)$ hides $\textrm{poly}(\log \log n)$ dependencies. This is the first non-adaptive algorithm in this setting achieving $\textrm{poly}(1/ε,\log n)$ query complexity. Prior work requires $Ω(\log^2 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 $\tilde O(ε^{-6} \log^{6} n)$, improving on the works of Dell et al. (SODA '20) and Bhattacharya et al. (STACS '22), which require $Ω(\log^3 n)$ rounds of adaptivity. Finally, as a consequence of our edge sampling algorithm, we obtain a $\tilde O(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^2)$ queries.
