论文标题
多项式时间中的最佳顶点耐断层跨度
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
论文作者
论文摘要
Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer $k$, every $n$-node graph has a $(2k-1)$-spanner on $O(f^{1-1/k} n^{1+1/k})$ edges resilient to $f$ vertex faults, and there are examples of input graphs on which this bound cannot be改进。但是，这些证据通过分析某种指数时间贪婪算法的输出跨度来起作用。在这项工作中，我们给出了第一种算法，该算法会产生最佳尺寸的顶点容错的跨度，并且在多项式时间内运行。具体来说，我们给出了一个随机算法，该算法采用$ \ widetilde {o} \ left（f^{1-1/k} n^{2 + 1/k} + mf^2 \ right）$ time。我们还将我们的算法取代以具有相似界限的确定性算法。这反映了[Bodwin-Patel PODC '19]的运行时的指数改善，这是唯一已知的算法，用于构建最佳的顶点耐受耐受性跨度。
Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer $k$, every $n$-node graph has a $(2k-1)$-spanner on $O(f^{1-1/k} n^{1+1/k})$ edges resilient to $f$ vertex faults, and there are examples of input graphs on which this bound cannot be improved. However, these proofs work by analyzing the output spanner of a certain exponential-time greedy algorithm. In this work, we give the first algorithm that produces vertex fault tolerant spanners of optimal size and which runs in polynomial time. Specifically, we give a randomized algorithm which takes $\widetilde{O}\left( f^{1-1/k} n^{2+1/k} + mf^2\right)$ time. We also derandomize our algorithm to give a deterministic algorithm with similar bounds. This reflects an exponential improvement in runtime over [Bodwin-Patel PODC '19], the only previously known algorithm for constructing optimal vertex fault-tolerant spanners.
