A Note on Fault Tolerant Reachability for Directed Graphs
Loukas Georgiadis1

Robert E. Tarjan2

arXiv:1511.07741v1 [] 24 Nov 2015

February 26, 2018

In this note we describe an application of low-high orders [2] in fault-tolerant network design.
Baswana et al. [1] study the following reachability problem. We are given a flow graph G = (V, A)
with start vertex s, and a spanning tree T = (V, AT ) rooted at s. We call a set of arcs A′ valid if
the subgraph G′ = (V, AT ∪ A′ ) of G has the same dominators as G. The goal is to find a valid set
of minimum size. Baswana et al. [1] show that there is a valid set containing at most n − 1 arcs,
and they give an algorithm to compute a minimum-size valid set in O(m log n) time, where n = |V |
and m = |A|. Their algorithm is based on generalizing the notion of semi-dominators [3] from a
depth-first spanning tree to an arbitrary spanning tree.
Here we give a simple algorithm, Algorithm 9 below, to compute a minimum-size valid set in
O(m) time, given the dominator tree D and a low-high order of it. Since D and a low-high order
can be computed in O(m) time [2], so can a minimum-size valid set.
Algorithm 9: Construction of a minimum-size valid set A′
Initialize A′ to be empty. For each vertex v 6= s, apply the appropriate one of the following cases,
where t(v) and d(v) are the parent of v in T and D respectively (d(v) is the immediate dominator
of v):
Case 1: t(v) = d(v). Do nothing.
Case 2: t(v) 6= d(v) and (d(v), v) ∈ A. Add (d(v), v) to A′ .
Case 3: (d(v), v) 6∈ A.
Subcase 3a: t(v) > v. Add to A′ an arc (x, v) with x < v.
Subcase 3b: t(v) < v. Add to A′ an arc (x, v) with x > v and x not a descendant of v in D.

Theorem 1. The set A′ computed by Algorithm 9 is a minimum-size valid set.
Proof. First, we show that in each occurrence of Cases 2 and 3, an arc will be added to A′ . This is
obvious for Case 2. To show that this is true for Case 3, we use the definition of a low-high order
[2, Section 2]: for any vertex v 6= s such that (d(v), v) 6∈ A, there are two arcs (u, v) and (w, v)
such that u < v < w and w is not a descendant of v in D. Only one of these arcs can be in T . It
1

Department of Computer Science & Engineering, University of Ioannina, Greece. E-mail: loukas@cs.uoi.gr.
Department of Computer Science, Princeton University, 35 Olden Street, Princeton, NJ, 08540, and Intertrust
Technologies. E-mail: ret@cs.princeton.edu.
2

1

follows that in both Case 3a and Case 3b, there is an arc that satisfies the stated constraint, and
hence such an arc will be added to A′ .
Second, we show that A′ is valid. To do this, we use the notion of a pair of divergent spanning
trees from [2]. Two spanning trees B and R, both rooted at s, are divergent if, for every vertex
v, the paths from s to v in B and R have only the dominators of v in common. Algorithm 1′
below, which simplifies Algorithm 1 in [2] as discussed just before Theorem 2.10 in [2], constructs
two divergent spanning trees, provided that each step is successful: the proof of Theorem 2.8 in [2]
applies to Algorithm 1′ equally as well as to the original Algorithm 1. Indeed, as does Algorithm
1, Algorithm 1′ constructs a pair of strongly divergent spanning trees, but here we need only the
weaker property of divergence.
Algorithm 1′ : Construction of Two Divergent Spanning Trees B and R
Let D be the dominator tree of flow graph G = (V, A), with a preorder that is a low-high order of
G. For each vertex v 6= s, apply the appropriate one of the following cases to choose arcs (b(v), v)
in B and (r(v), v) in R:
Case 1: (d(v), v) ∈ A. Set b(v) = r(v) = t(v).
Case 2: (d(v), v) 6∈ A. Choose two arcs (u, v) and (w, v) such that u < v < w in low-high order
and w is not a descendant of v in D. Set b(v) = u and r(v) = w.
Suppose we apply Algorithm 1′ to G, but only allow it to choose arcs that are in subgraph G′ .
Suppose Case 1 of Algorithm 1′ applies to v. Then (d(v), v) is in G. But the construction of A′
guarantees that (d(v), v) is in G′ as well. Hence this case will add an arc in G′ , namely (d(v), v), to
both B and R. Suppose Case 2 of Algorithm 1′ applies to v. Then (d(v), v) is not in G. Algorithm 9
will apply Case 3 to v, which guarantees that G′ contains arcs (u, v) and (w, v) such that u < v < w
(in low-high order) and w is not a descendant of v in D: if t(v) > v, t(v) cannot be a descendant of
v in D since there is a v-avoiding path in T from s to t(v). Hence this case can successfully choose
arcs in G′ to add to B and R. We conclude that G′ contains two spanning trees that are divergent
in G. It follows that if v dominates w in G′ , v dominates w in G. The converse is immediate, since
G′ is a subgraph of G. Thus A′ is valid.
Finally, we show that A′ is minimum-size. Set A′ contains an arc (u, v) only if t(v) 6= d(v).
Any valid set must contain an arc entering v, since otherwise t(v) dominates v in G′ , contradicting
validity.

References
[1] S. Baswana, K. Choudhary, and L. Roditty. Fault tolerant reachability for directed graphs.
In Yoram Moses, editor, Distributed Computing, volume 9363 of Lecture Notes in Computer
Science, pages 528–543. Springer Berlin Heidelberg, 2015.
[2] L. Georgiadis and R. E. Tarjan. Dominator tree certification and divergent spanning trees.
ACM Transactions on Algorithms, 12(1):11:1–11:42, November 2015.
[3] T. Lengauer and R. E. Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM
Transactions on Programming Languages and Systems, 1(1):121–41, 1979.

2

