Fault Tolerant Reachability, DFS Tree, and Min-cut

Consider the following problem of single source reachability under failures of vertices or edges. Let $G$ be a given directed graph on n vertices with a designated source vertex $s$ , and $k$ be any positive integer.  Compute the sparsest subgraph of $G$ that preserves reachability from s upon failure of any k vertices/edges.

In this talk, we shall discuss two algorithms that construct such a subgraph based on respectively DFS tree and min-cut: two elementary and distinct concepts seemingly unrelated to the problem. The first algorithm, that works only for the special case of $k = 1$, is based on a DFS tree rooted at $s$ . This solution can be seen as a byproduct of the seminal work on dominators by Lengeuer and Tarjan in 1979. The corresponding subgraph will always have less than 2$n$ edges. The algorithm for any general value of $k$ was derived after 35 years. This algorithm turns out to be based on farthest min-cut : a term coined by Ford and Fulkerson in their 1962 research paper on the first algorithm for max-flow. The corresponding subgraph will have $O(n2k)$ edges. We also prove a matching lower bound (this is a joint work with Keerti Choudhary (a PhD student at IITK) and Liam Roditty (Bar-Ilan University)).