A Note on Fault Tolerant Reachability for Directed Graphs

Abstract

In this note we describe an application of low-high orders in fault-tolerant network design. Baswana et al. [DISC 2015] study the following reachability problem. We are given a flow graph $G=(V,A)$ with start vertex $s$, and a spanning tree $T=(V,A_T)$ rooted at $s$. We call a set of arcs $A^{\prime }$ valid if the subgraph $G^{\prime }=(V,A_T\cup A^{\prime })$ of $G$ has the same dominators as $G$. The goal is to find a valid set of minimum size. Baswana et al. gave an $O(m\log n)$-time algorithm to compute a minimum-size valid set in $O(m\log n)$ time, where $n=|V|$ and $m=|A|$. Here we provide a simple $O(m)$-time algorithm that uses the dominator tree $D$ of $G$ and a low-high order of it.