Talks - Fall 2017








Compact and Efficient Fault Tolerant Structures for Directed Graphs

Keerti Choudhary

25 Aug, 2017

3:30 PM


Single source reachability, Shortest path tree, Strong connectivity, etc. are some of the most fundamental problems in graph algorithms. In the static setting each of these problems can be solved in $O(n+m)$ time, where $n$ and $m$ are respectively the number of vertices and edges in the graph. However, most of the applications in real life deal with graphs which are prone to failures. These failures are both small in number and transient in nature. This aspect is generally captured by associating a parameter $k$ with the network such that there are at most $k$ vertices (or edges) that are failed at any stage. Here $k$ is much smaller than the number of vertices in the underlying graph. Our main goal is to compute data structures that can achieve robustness by being functional even after occurrence of failures. The three main objectives studied in this scenario are: (i) computing a compact data structure (oracle) that can quickly answer any query for a given problem (e.g. distance, connectivity, etc.) on occurrence of any $k$ failures, (ii) designing a compact routing scheme in network avoiding the failed nodes/edges, and (iii) computing a sparse subgraph that preserves a certain property (e.g. shortest path, connectedness, etc.) of the graph even after failures have occurred. We address one or more of these objectives for some of the fundamental problems in the fault tolerant model for directed graphs.

We first consider the problem of computing a sparse subgraph that preserves the reachability from a designated source even after the failure of any $k$ edges or vertices. We settle this problem for any $k>1$, by showing an upper bound of $2^{k}n$. We also show that this bound is tight by proving a lower bound of $\Omega(2^{k}n)$. Next, we obtain a fault tolerant oracle for answering reachability queries from a designated source on failure of any two vertices in constant time. For the strong connectivity problem, we obtain an oracle that after any $k$ failures can report all the strongly connected components of the remaining graph in $O(2^{k}n\log^2 n)$ time. Our reporting time is optimal (up to logarithmic factors) for any fixed value of $k$. We also address the problem of maintaining a $(1+\epsilon)$-approximate shortest path of a directed weighted graph from a fixed source in the presence of a failure of an edge or a vertex. We obtain near optimal results for oracle, subgraph and routing for this problem. Also we show that space used by our oracle and subgraph is optimal upto logarithmic factors by providing a matching lower bound.




Sumanta Ghosh

Head Co-ordinator


Rajendra Kumar



Mahesh S R