Fault Tolerant Reachability for Directed Graphs

Surender Baswana (1) , Keerti Choudhary (1) , Liam Roditty (2)

1 CSE - Department of Computer Science and Engineering [Kanpur]
2 Department of Computer Science [Bar Ilan]

Let G = (V,E) be an n-vertices m-edges directed graph. Let s ∈ V be any designated source vertex, and let T be an arbitrary reachability tree rooted at s. We address the problem of finding a set of edges E ⊆ E\T of minimum size such that on a failure of any vertex w ∈ V, the set of vertices reachable from s in T∪E\{w} is the same as the set of vertices reachable from s in G\{w}. We obtain the following results: 1) The optimal set E for any arbitrary reachability tree T has at most n − 1 edges. 2) There exists an O(m log n)-time algorithm that computes the optimal set E for any given reachability tree T . For the restricted case when the reachability tree T is a Depth-First-Search (DFS) tree it is straightforward to bound the size of the optimal set E by n − 1 using semidominators with respect to DFS trees from the celebrated work of Lengauer and Tarjan [13]. Such a set E can be computed in O(m) time using the algorithm of Buchsbaum et. al [4]. To bound the size of the optimal set in the general case we define semidominators with respect to arbitrary trees. We also present a simple O(m log n) time algorithm for computing such semidominators. As a byproduct, we get an alternative algorithm for computing dominators in O(m log n) time.

Domains: Distributed, Parallel, and Cluster Computing [cs.DC]

Surender Baswana, Keerti Choudhary, Liam Roditty. Fault Tolerant Reachability for Directed Graphs. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_35⟩. ⟨hal-01207207⟩