#### Compact and Efficient Fault Tolerant Structures for Directed Graphs

#### Keerti Choudhary

#### 25 Aug, 2017

#### 3:30 PM

#### KD103

#### 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.