Liam Roditty (Bar-Ilan University)
Wednesday, 27.12.2017, 12:30
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.