Tata Institute of Fundamental Research
Fault Tolerant Reachability, DFS Tree, and Min-cut
STCS Colloquium
Speaker:
Surender Baswana (Indian Institute of Technology
Department of Computer Science and Engineering
Kanpur 208016)
Organiser:
Jaikumar Radhakrishnan
Date:
Thursday, 16 Mar 2017, 14:00 to 15:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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)).
| Speaker: | Surender Baswana (Indian Institute of Technology Department of Computer Science and Engineering Kanpur 208016) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Thursday, 16 Mar 2017, 14:00 to 15:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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)).
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)).