论文标题
寻找隐藏的边缘
Finding a Hidden Edge
论文作者
论文摘要
我们考虑在隐藏的无向图中找到边缘的问题$ g =（v，e）$带有$ n $ vertices，在一个模型中，我们只允许询问顶点子集是否包含边缘的查询。我们研究了非自适应模型，并表明，在确定性模型中，最佳算法需要$ \ binom {n} {2} {2} $ queries（即，在随机模型$ \tildeθ（n）$ queries中（需要分别查询任何可能的边缘），以便找到一个边缘。 此外，我们研究了特定图表的查询复杂性，包括恒星，集团和匹配项，用于随机模型和确定性模型。 最后，对于一般图，我们显示了查询复杂性与自适应算法制造的回合数量（$ r $）之间的权衡。我们以$ o（rn^{2/r}）$和$ \ tilde {o}（rn^{1/r}）$示例确定性和随机模型的样本复杂性，以$ o（rn^{2/r}）$介绍两种算法。
We consider the problem of finding an edge in a hidden undirected graph $G = (V, E)$ with $n$ vertices, in a model where we only allowed queries that ask whether or not a subset of vertices contains an edge. We study the non-adaptive model and show that while in the deterministic model the optimal algorithm requires $\binom{n}{2}$ queries (i.e., querying for any possible edge separately), in the randomized model $\tildeΘ(n)$ queries are sufficient (and needed) in order to find an edge. In addition, we study the query complexity for specific families of graphs, including Stars, Cliques, and Matchings, for both the randomized and deterministic models. Lastly, for general graphs, we show a trade-off between the query complexity and the number of rounds, $r$, made by an adaptive algorithm. We present two algorithms with $O(rn^{2/r})$ and $\tilde{O}(rn^{1/r})$ sample complexity for the deterministic and randomized models, respectively.
