  In this paper we study the problem of maintaining the strongly connected
components of a graph in the presence of failures. In particular, we show that
given a directed graph $G=(V,E)$ with $n=|V|$ and $m=|E|$, and an integer value
$k\geq 1$, there is an algorithm that computes in $O(2^{k}n\log^2 n)$ time for
any set $F$ of size at most $k$ the strongly connected components of the graph
$G\setminus F$. The running time of our algorithm is almost optimal since the
time for outputting the SCCs of $G\setminus F$ is at least $\Omega(n)$. The
algorithm uses a data structure that is computed in a preprocessing phase in
polynomial time and is of size $O(2^{k} n^2)$.
  Our result is obtained using a new observation on the relation between
strongly connected components (SCCs) and reachability. More specifically, one
of the main building blocks in our result is a restricted variant of the
problem in which we only compute strongly connected components that intersect a
certain path. Restricting our attention to a path allows us to implicitly
compute reachability between the path vertices and the rest of the graph in
time that depends logarithmically rather than linearly in the size of the path.
This new observation alone, however, is not enough, since we need to find an
efficient way to represent the strongly connected components using paths. For
this purpose we use a mixture of old and classical techniques such as the heavy
path decomposition of Sleator and Tarjan and the classical Depth-First-Search
algorithm. Although, these are by now standard techniques, we are not aware of
any usage of them in the context of dynamic maintenance of SCCs. Therefore, we
expect that our new insights and mixture of new and old techniques will be of
independent interest.
