Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
复制标题
最佳顶点容错扳手（用于固定拉伸）
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
V. V. Williams
中科院分区：
文献类型：
--
作者：
Gregory Bodwin;M. Dinitz;M. Parter;V. V. Williams
图\(G\)的一个\(k\)-生成树是一个稀疏子图\(H\)，其最短路径距离与\(G\)的最短路径距离相比，误差最多为\(k\)倍。在本文中，我们研究对故障有抵抗力的生成树。如果对于任何可能“失效”的\(f\)个顶点的小子集\(F\)，\(H\setminus F\)是\(G\setminus F\)的一个\(k\)-生成树，那么子图\(H\subseteq G\)是一个\(f\)个顶点容错（VFT）\(k\)-生成树。该领域的一个主要问题是：对于所有\(n\)个节点的图，一个\(f\)个顶点容错\(k\)-生成树的最小规模是多少（作为\(f\)、\(k\)和\(n\)的函数）？这个问题首先在几何图的背景下被研究[Levcopoulos等人，STOC '98，Czumaj和Zhao，SoCG '03]，最近在一般无向图中也被考虑[Chechik等人，STOC '09，Dinitz和Krauthgamer，PODC '11]。
在本文中，我们在拉伸因子\(k\)固定的情况下解决了VFT生成树的最优规模问题。具体来说，我们证明每个（无向的，可能有权重的）\(n\)个节点的图\(G\)都有一个对\(f\)个顶点故障有抵抗力的\((2k - 1)\)-生成树，它有\(O_k(f^{1 - 1/k}n^{1 + 1/k})\)条边，并且这是完全最优的（除非著名的厄尔多斯围长猜想是错误的）。我们的下界甚至可以推广到意味着在最坏情况下，没有能够类似地近似\(dist_{G\setminus F}(s,t)\)的数据结构在空间使用上能优于我们的生成树。我们还考虑了边容错（EFT）模型，它与边故障而非顶点故障类似地定义。我们表明在这种情况下同样的生成树上界适用。我们的数据结构下界扩展到\(k = 2\)的情况（因此我们解决了\(3\)-近似的EFT问题），但对于\(k\geq3\)，它降至\(\Omega(f^{1/2 - 1/(2k)}\cdot n^{1 + 1/k})\)。我们将缩小这个差距作为一个开放问题留下。
A $k$-spanner of a graph $G$ is a sparse subgraph $H$ whose shortest path distances match those of $G$ up to a multiplicative error $k$. In this paper we study spanners that are resistant to faults. A subgraph $H \subseteq G$ is an $f$ vertex fault tolerant (VFT) $k$-spanner if $H \setminus F$ is a $k$-spanner of $G \setminus F$ for any small set $F$ of $f$ vertices that might "fail." One of the main questions in the area is: what is the minimum size of an $f$ fault tolerant $k$-spanner that holds for all $n$ node graphs (as a function of $f$, $k$ and $n$)? This question was first studied in the context of geometric graphs [Levcopoulos et al. STOC '98, Czumaj and Zhao SoCG '03] and has more recently been considered in general undirected graphs [Chechik et al. STOC '09, Dinitz and Krauthgamer PODC '11].
In this paper, we settle the question of the optimal size of a VFT spanner, in the setting where the stretch factor $k$ is fixed. Specifically, we prove that every (undirected, possibly weighted) $n$-node graph $G$ has a $(2k-1)$-spanner resilient to $f$ vertex faults with $O_k(f^{1 - 1/k} n^{1 + 1/k})$ edges, and this is fully optimal (unless the famous Erdos Girth Conjecture is false). Our lower bound even generalizes to imply that no data structure capable of approximating $dist_{G \setminus F}(s, t)$ similarly can beat the space usage of our spanner in the worst case. We also consider the edge fault tolerant (EFT) model, defined analogously with edge failures rather than vertex failures. We show that the same spanner upper bound applies in this setting. Our data structure lower bound extends to the case $k=2$ (and hence we close the EFT problem for $3$-approximations), but it falls to $\Omega(f^{1/2 - 1/(2k)} \cdot n^{1 + 1/k})$ for $k \ge 3$. We leave it as an open problem to close this gap.
受顶点故障影响的图的连接预言
影响因子：
1.6
作者：
Duan, Ran;Pettie, Seth
通讯作者：
Pettie, Seth