论文标题
pptimal顶点耐故障跨度在§时间：顺序，分布和平行
Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel
论文作者
论文摘要
我们（几乎）解决了具有最佳稀疏性（到多毛因子）的计算顶点耐受耐受（VFT）跨度的时间复杂性。在存在顶点故障的情况下，VFT跨度是稀疏的子图，可保留距离信息，最多可延伸。这些结构是由[Chechik等，Stoc 2009]引入的，此后引起了很多关注。我们提供用于计算任何$ n $ vertex $ m $ - edge图的算法，用于计算几乎最佳的$ f $ -vft跨度，并在几种计算模型中具有接近最佳的运行时间： - 一种随机顺序算法，其运行时为$ \ widetilde {o}（m）$（即，故障数$ f $）。最新的时间限制为$ \ widetilde {o}（f^{1-1/k} \ cdot n^{2+1/k}+f^2 m）$ by [Bodwin，Dinitz和Robelle，Sode 2021]。 - $ \ widetilde {o}（1）$ roughs的分布式拥堵算法。改进[Dinitz and Robelle，PODC 2020]，在$ \ widetilde {o}（f^{2}）$ rounds中获得了近距离稀疏的ft跨度。 - 带有$ \ widetilde {o}（m）$ work和$ \ widetilde {o}（1）$ depth的婴儿车（CRCW）算法。 [Dinitz和Krauthgamer，PODC 2011]隐含的先前界限使用了$ \ wideTilde {o}（f^3m）$ Work和$ \ wideTilde {o}（o}（f^3）$ depth。 立即推论提供了使用Polylogarithmic Depth和接近线性工作的第一个几乎最佳的婴儿车算法，用于计算几乎最佳的$λ$ - \ emph {vertex}连接证书。这改善了[Karger and Motwani，stoc'93]的$ \ widetilde {o}（1）$ depth和$ o（λm）$的最新并行边界。
We (nearly) settle the time complexity for computing vertex fault-tolerant (VFT) spanners with optimal sparsity (up to polylogarithmic factors). VFT spanners are sparse subgraphs that preserve distance information, up to a small multiplicative stretch, in the presence of vertex failures. These structures were introduced by [Chechik et al., STOC 2009] and have received a lot of attention since then. We provide algorithms for computing nearly optimal $f$-VFT spanners for any $n$-vertex $m$-edge graph, with near optimal running time in several computational models: - A randomized sequential algorithm with a runtime of $\widetilde{O}(m)$ (i.e., independent in the number of faults $f$). The state-of-the-art time bound is $\widetilde{O}(f^{1-1/k}\cdot n^{2+1/k}+f^2 m)$ by [Bodwin, Dinitz and Robelle, SODA 2021]. - A distributed congest algorithm of $\widetilde{O}(1)$ rounds. Improving upon [Dinitz and Robelle, PODC 2020] that obtained FT spanners with near-optimal sparsity in $\widetilde{O}(f^{2})$ rounds. - A PRAM (CRCW) algorithm with $\widetilde{O}(m)$ work and $\widetilde{O}(1)$ depth. Prior bounds implied by [Dinitz and Krauthgamer, PODC 2011] obtained sub-optimal FT spanners using $\widetilde{O}(f^3m)$ work and $\widetilde{O}(f^3)$ depth. An immediate corollary provides the first nearly-optimal PRAM algorithm for computing nearly optimal $λ$-\emph{vertex} connectivity certificates using polylogarithmic depth and near-linear work. This improves the state-of-the-art parallel bounds of $\widetilde{O}(1)$ depth and $O(λm)$ work, by [Karger and Motwani, STOC'93].
