Prof. Meirav Zehavi

Let G be a directed graph with n vertices and m edges, and let s∈V(G) be a designated source vertex. We consider the problem of single source reachability (SSR) from s in presence of failures of edges (or vertices). Formally, a spanning subgraph H of G is a {\em k-Fault Tolerant Reachability Subgraph (k-FTRS)} if it has the following property. For any set F of at most k edges (or vertices) in G, and for any vertex v∈V(G), the vertex v is reachable from s in G−F if and only if it is reachable from s in H−F. Baswana this http URL. [STOC 2016, SICOMP 2018] showed that in the setting above, for any positive integer k, we can compute a k-FTRS with 2kn edges. In this paper, we give a much simpler algorithm for computing a k-FTRS, and observe that it extends to higher connectivity as well. Our results follow from a simple application of \emph{important separators}, a well known technique in Parameterized Complexity.