Fault tolerant subgraph for single source reachability: generic and optimal
Fault tolerant subgraph for single source reachability: generic and optimal
复制标题
单源可达性的容错子图：通用和最优
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
L. Roditty
中科院分区：
文献类型：
--
作者：
Surender Baswana;Keerti Choudhary;L. Roditty
设\(G=(V,E)\)是一个有\(n\)个顶点和\(m\)条边的有向图。设\(s\in V\)是任意指定的源顶点。我们研究在顶点/边出现故障的情况下从\(s\)出发的单源可达性（SSR）问题。我们证明对于每个\(k\geq1\)，\(G\)存在一个子图\(H\)，其边数至多为\(2kn\)，即使在任意\(k\)条边出现故障后，仍能保持从\(s\)的可达性。形式上，给定一个由\(k\)条边组成的集合\(F\)，顶点\(u\in V\)在\(G\setminus F\)中从\(s\)可达当且仅当\(u\)在\(H\setminus F\)中从\(s\)可达。我们称\(H\)为一个\(k\) - 容错可达性子图（\(k - FTRS\)）。我们还证明了对于此类子图的一个匹配下界为\(\Omega(2kn)\)。我们的结果可推广到顶点故障情况，且无任何额外开销。
\(k - FTRS\)的一般构造从几个不同的角度来看都很有趣。从图论的角度来看，它揭示了有向图中SSR和单源最短路径（SSSP）之间的差异。更具体地说，在加权有向图的SSSP情况下，即使对于单条边故障，也存在一个\(\Omega(m)\)的下界。在无权图的情况下，即使对于单条边故障，也存在一个\(\Omega(n^{3/2})\)条边的下界。也存在一个匹配的上界，但对于有向图中两条或更多条边故障的情况一无所知。
从算法的角度来看，它意味着对其他有趣问题的容错解决方案，即（i）验证在\(k\)条边或顶点故障后图的强连通性是否保持，（ii）计算在\(k\)次故障后的图的支配树。从技术的角度来看，它对最远最小割的概念进行了有趣的应用，该概念已由福特和富尔克森在他们关于流和割的开创性工作中提出。我们表明最远最小割和\(k - FTRS\)之间存在密切关系。我们相信我们的新技术具有独立的研究价值。
Let G=(V,E) be an n-vertices m-edges directed graph. Let s∈ V be any designated source vertex. We address the problem of single source reachability (SSR) from s in presence of failures of vertices/edges. We show that for every k≥ 1, there is a subgraph H of G with at most 2k n edges that preserves the reachability from s even after the failure of any k edges. Formally, given a set F of k edges, a vertex u∈ V is reachable from s in G∖ F if and only if u is reachable from s in H∖ F. We call H a k-Fault Tolerant Reachability Subgraph (k-FTRS). We prove also a matching lower bound of Ω(2kn) for such subgraphs. Our results extend to vertex failures without any extra overhead. The general construction of k-FTRS is interesting from several different perspectives. From the Graph theory perspective it reveals a separation between SSR and single source shortest paths (SSSP) in directed graphs. More specifically, in the case of SSSP in weighted directed graphs, there is a lower bound of Ω(m) even for a single edge failure. In the case of unweighted graphs there is a lower bound of Ω(n3/2) edges, again, even for a single edge failure. There is also a matching upper bound but nothing is known for two or more failures in the directed graphs. From the Algorithms perspective it implies fault tolerant solutions to other interesting problems, namely, (i) verifying if the strong connectivity of a graph is preserved after k edge or vertex failures, (ii) computing a dominator tree of a graph after k-failures. From the perspective of Techniques it makes an interesting usage of the concept of farthest min-cut which was already introduced by Ford and Fulkerson in their pioneering work on flows and cuts. We show that there is a close relationship between the farthest min-cut and the k-FTRS. We believe that our new technique is of independent interest.