The Taub Faculty of Computer Science Events and Talks

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 2^k 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 Ω(2^kn) 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 Ω(n^3/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. Our algorithm 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.