Fault Tolerant Reachability for Directed Graphs

Let

G

 = (

V

,

E

) be an

n

-vertices

m

-edges directed graph. Let

s

 ∈ 

V

be any designated source vertex, and let

T

be an arbitrary reachability tree rooted at

s

. We address the problem of finding a set of edges

${\cal E}\subseteq E\backslash T$

of minimum size such that on a failure of any vertex

w

 ∈ 

V

, the set of vertices reachable from

s

in

$T\cup{\cal E} \backslash \{w\}$

is the same as the set of vertices reachable from

s

in

G

\{

w

}. We obtain the following results:

The optimal set

$\cal E$

for any arbitrary reachability tree

T

has at most

n

 − 1 edges.

There exists an

O

(

m

log

n

)-time algorithm that computes the optimal set

${\mathcal E}$

for any given reachability tree

T

.

For the restricted case when the reachability tree

T

is a Depth-First-Search (DFS) tree it is straightforward to bound the size of the optimal set

${\mathcal E}$

by

n

 − 1 using semidominators with respect to DFS trees from the celebrated work of Lengauer and Tarjan [13]. Such a set

$\cal E$

can be computed in

O

(

m

) time using the algorithm of Buchsbaum et. al [4].

To bound the size of the optimal set in the general case we define semidominators with respect to arbitrary trees. We also present a simple

O

(

m

log

n

) time algorithm for computing such semidominators. As a byproduct, we get an alternative algorithm for computing dominators in

O

(

m

log

n

) time.