Graph connectivity is a fundamental combinatorial optimization problem that arises in many practical applications, where usually a spanning subgraph of a network is used for its operation. However, in the real world, links may fail unexpectedly deeming the networks non-operational, while checking whether a link is damaged is costly and possibly erroneous. After an event that has damaged an arbitrary subset of the edges, the network operator must find a spanning tree of the network using non-damaged edges by making as few checks as possible. Motivated by such questions, we study the problem of finding a spanning tree in a network, when we only have access to noisy queries of the form "Does edge e exist?". We design efficient algorithms, even when edges fail adversarially, for all possible error regimes; 2-sided error (where any answer might be erroneous), false positives (where "no" answers are always correct) and false negatives (where "yes" answers are always correct). In the first two regimes we provide efficient algorithms and give matching lower bounds for general graphs. In the False Negative case we design efficient algorithms for large interesting families of graphs (e.g. bounded treewidth, sparse). Using the previous results, we provide tight algorithms for the practically useful family of planar graphs in all error regimes.
翻译:图形连接是一个基本的组合优化问题, 在许多实际应用中, 通常使用网络的横贯子图进行操作。 然而, 在现实世界中, 链接可能会意外地不认为网络不运作, 同时检查链接是否受损是昂贵的, 也可能是错误的。 在损坏了任意的边缘子集的事件后, 网络操作员必须找到一个使用无损伤边缘的覆盖网络的树, 并尽可能少地进行检查。 受这些问题的驱使, 我们研究在网络中找到覆盖树的问题, 当我们只能获得“ 边缘 e 存在 ” 形式的响亮查询时 。 我们设计高效的算法, 即使边缘在对抗性失败时, 对所有可能的错误制度都是如此 。 2 偏差( 任何答案都可能错误 ), “ 不 答案总是正确 ” ) 和 虚假的负差( 在“ 肯定” 答案总是正确的地方 ) 。 在前两个制度中, 我们提供高效的算法, 并给一般图表下下下下下下下框。 在 Falfal URus 中, 我们设计高效的算算法, 。 我们设计了大家族的直径的直径直径直图。 。 。