All-Pairs 2-Reachability in O(nω log n) Time.
Loukas Georgiadis1 , Daniel Graf2 , Giuseppe F. Italiano∗3 , Nikos Parotsidis3 , and
Przemysław Uznański2
1

University of Ioannina, Greece., loukas@cs.uoi.gr
of Computer Science, ETH Zürich, Switzerland., daniel.graf@inf.ethz.ch,
przemyslaw.uznanski@inf.ethz.ch
3 University of Rome Tor Vergata, Italy., giuseppe.italiano@uniroma2.it,
nikos.parotsidis@uniroma2.it

arXiv:1612.08075v2 [] 26 Jul 2017

2 Department

Abstract
In the 2-reachability problem we are given a directed graph G and we wish to determine if
there are two (edge or vertex) disjoint paths from u to v, for a given pair of vertices u and v.
In this paper, we present an algorithm that computes 2-reachability information for all pairs of
vertices in O(nω log n) time, where n is the number of vertices and ω is the matrix multiplication
exponent. Hence, we show that the running time of all-pairs 2-reachability is only within a log
factor of transitive closure.
Moreover, our algorithm produces a witness (i.e., a separating edge or a separating vertex)
for all pair of vertices where 2-reachability does not hold. By processing these witnesses, we
can compute all the edge- and vertex-dominator trees of G in O(n2 ) additional time, which in
turn enables us to answer various connectivity queries in O(1) time. For instance, we can test in
constant time if there is a path from u to v avoiding an edge e, for any pair of query vertices u
and v, and any query edge e, or if there is a path from u to v avoiding a vertex w, for any query
vertices u, v, and w.

1

Introduction

The all-pairs reachability problem consists of preprocessing a directed graph (digraph) G = (V, E)
so that we can answer queries that ask if a vertex y is reachable from a vertex x. This problem
has many applications, including databases, geographical information systems, social networks, and
bioinformatics [14]. A classic solution to this problem is to compute the transitive closure matrix of
G, either by performing a graph traversal (e.g., depth-first or breadth-first search) once per each
vertex as source, or via matrix multiplication. For a digraph with n vertices and m edges, the former
solution runs in O(mn) time, while the latter runs in O(nω ), where ω is the matrix multiplication
exponent [5, 16, 24]. Here we study a natural generalization of the all-pairs reachability problem,
that we refer to as all-pairs 2-reachability, where we wish to preprocess G so that we can answer fast
the following type of queries: For a given vertex pair x, y ∈ V , are there two edge-disjoint (resp.,
∗
Partially supported by MIUR, the Italian Ministry of Education, University and Research, under Project AMANDA
(Algorithmics for MAssive and Networked DAta).

1

internally vertex-disjoint) paths from x to y? Equivalently, by Menger’s theorem [18], we ask if there
is an edge e ∈ E (resp., a vertex z ∈ V ) such that there is no path from x to y in G \ e (resp., G \ z).
We call such an edge (resp., vertex) separating for the pair x, y.
One solution to the all-pairs 2-reachability problem is to compute all the dominator trees of G,
with each vertex as source. The dominator tree of G with start vertex s is a tree rooted at s, such
that a vertex v is an ancestor of a vertex w if and only if all paths from s to w include v [17]. All the
separating edges and vertices for a pair s, v, appear on the path from s to v in the dominator tree
rooted at s, in the same order as they appear in any path from s to v in G. Given all the dominator
trees, we can process them to compute the 2-reachability information for all pairs of vertices (see
Section 8). Since a dominator tree can be computed in O(m) time [2, 4], the overall running time of
this algorithm is O(mn).
Our Results. In this paper, we show how to beat the O(nm) bound for dense graphs. Specifically,
we present an algorithm that computes 2-reachability information for all pairs of vertices in O(nω )
time in a strongly connected digraph, and in O(nω log n) time in a general digraph. Hence, we show
that the running time of all-pairs 2-reachability is only within a log factor of transitive closure.
This result is tight up to a log factor, since it can be shown that all-pairs 2-reachability is at least
as hard as computing the transitive closure, which is asymptotically equivalent to Boolean matrix
multiplication [8]. Moreover, our algorithm produces a witness (separating edge or separating vertex)
whenever 2-reachability does not hold. By processing these witnesses, we can find all the dominator
trees of G in O(n2 ) additional time. Thus, we also show how to compute all the dominator trees of
a digraph in O(nω log n) time (in O(nω ) time if the graph is strongly connected), which improves
the previously known O(mn) bound for dense graphs. This in turn enables us to answer various
connectivity queries in O(1) time. For instance, we can test in O(1) time if there is a path from u to
v avoiding an edge e, for any pair of query vertices u and v, and any query edge e, or if there is a
path from u to v avoiding a vertex w, for any query vertices u, v, and w. We can also report all the
edges or vertices that appear in all paths from u to v, for any query vertices u and v.
Related Work. To the best of our knowledge, ours is the first work that considers the all-pairs
2-reachability problem and gives a fast algorithm for it. In recent work Georgiadis et al. [11]
investigate the effect of an edge or a vertex failure in a digraph G with respect to strong connectivity.
Specifically, they show how to preprocess G in O(m + n) time in order to answer various sensitivity
queries regarding strong connectivity in G under an arbitrary edge or vertex failure. For instance,
they can compute in O(n) time the strongly connected components (SCCs) that remain in G after
the deletion of an edge or a vertex, or report various statistics such as the number of SCCs in
constant time per query (failed) edge or vertex. This result, however, cannot be applied for the
solution of the 2-reachability problem. The reason is that if the deletion of an edge e leaves two
vertices u and v in different SCCs in G \ e, the algorithm of [11] is not able to distinguish if there is
still a path or no path from u to v in G \ e.
Previously, King and Sagert [15] gave an algorithm that can quickly answer sensitivity queries
for reachability in a directed acyclic graph (DAG) [15]. Specifically, they show how to process a
DAG G so that, for any pair of query vertices x and y, and a query edge e, one can test in constant
time if there is a path from x to y in G \ e. Note that the result of King and Sagert does not yield
an efficient solution to the all-pairs 2-reachability problem, since we need O(m) queries just to find if
there is a separating edge for a single pair of vertices. Moreover, their preprocessing time is O(n3 ).
2

Another interesting fact that arises from our work is that, somewhat surprisingly, computing all
dominator trees in dense graphs is currently faster than computing a spanning arborescence from
each vertex. The best algorithm for this problem is given by Alon et al. [1], who studied the problem
of constructing a BFS tree from every vertex, and gave an algorithm that runs in O(n(3+ω)/2 ) time.
Our algorithm uses fast matrix multiplication. Several other important graph-theoretic and
network optimization problems can be solved by reductions to fast matrix multiplication. These
include finding maximum weight matchings [20], computing shortest paths [27], and finding least
common ancestors in DAGs [7] and junctions in DAGs [26]. Our algorithms can be used for
constant-time queries on whether there exists a path from vertex u to vertex v avoiding an edge e
(called avoiding path). This notion is closely related to a replacement path [12, 23, 25] (for which we
additionally require to be shortest in G \ e).
Our Techniques. Our result is based on two novel approaches, one for DAGs and one for strongly
connected digraphs. For DAGs we develop an algebra that operates on paths. We then use some
version of 1-superimposed coding to apply our path algebra in a divide and conquer approach. This
allows us to use Boolean matrix multiplication, in a similar vein to the computation of transitive
closure. Unfortunately, our algebraic approach does not work for strongly connected digraphs. In
this case, we exploit dominator trees in order to transform a strongly connected digraph G into
two auxiliary graphs, so as to reduce 2-reachability queries in G to 1-reachability queries in those
auxiliary graphs. This reduction works only for strongly connected digraphs and does not carry over
to general digraphs. Our algorithm for general digraphs is obtained via a careful combination of
those two approaches.
Organization. The remainder of the paper is organized as follows. After introducing some basic
definitions and notation in Section 2, we present our algorithm in three steps. In Section 3 we
describe our approach for acyclic graphs, Section 4 covers strongly connected graphs and Section 5
describes their combination for arbitrary digraphs. We provide a matching lower bound and extend
our approach to vertex-disjointness in Sections 6 and 7, respectively. Finally, Section 8 lists several
applications of our algorithm.

2

Preliminaries

We assume that the reader is familiar with standard graph terminology, as contained for instance
in [6]. Let G = (V, E) be a directed graph (digraph). Given an edge e = (x, y) in E, we denote
x (resp., y) as the tail (resp., head ) of e. A directed path in G is a sequence of vertices v1 , v2 , . . .,
vk , such that edge (vi , vi+1 ) ∈ E for i = 1, 2, . . . , k − 1. The path is said to contain vertex vi , for
i = 1, 2, . . . , k, and edge (vi , vi+1 ), for i = 1, 2, . . . , k − 1. The length of a directed path is given by
its number of edges. As a special case, there is a path of length 0 from each vertex to itself. We
write u v to denote that there is a path from u to v, and u6 v if there is no path from u to v.
A directed cycle is a directed path, with length greater than 0, starting and ending at the same
vertex. A directed acyclic graph (in short DAG) is a digraph with no cycles. A DAG has a topological
ordering, i.e., a linear ordering of its vertices such that for every edge (u, v), u comes before v in
the ordering (denoted by u < v). A digraph G is strongly connected if there is a directed path from
each vertex to every other vertex. The strongly connected components of a digraph are its maximal
strongly connected subgraphs. Given a subset of vertices V 0 ⊂ V , we denote by G \ V 0 the digraph
3

a

>
(a, b) (a, b) (a, b)
 (b, c)
>
(b, c)
>

(c, a) (c, a)
>
>

 ⊥
⊥
⊥
>
⊥
⊥
⊥
⊥


c
b

e

d


(a, b)
(d, e)

(d, e)

(d, e)
>

Figure 1: A graph and its (non-unique) 2-reachability closure matrix.
obtained after deleting all the vertices in V 0 , together with their incident edges. Given a subset of
edges E 0 ⊂ E, we denote by G \ E 0 the digraph obtained after deleting all the edges in E’.
2-Reachability and 2-Reachability closure. We write u 2e v (resp., u 2v v) to denote that
there are two edge-disjoint (resp., internally vertex-disjoint) paths from u to v, and u6 2e v (resp.,
u6 2v v) otherwise. As a special case, we assume that v 2e v (resp., v 2v v) for each vertex v in
G. We define an abstract set E + = E ∪ {>, ⊥}. The semantic of this set is as follows: e ∈ E
corresponds to an edge e separating two vertices, > corresponds to 2e (no single edge separates)
and ⊥ corresponds to 6 (no edge is necessary for separation, vertices are already separated). Given
a digraph G, we define the 2-reachability closure of G, denoted by G 2e , to be a matrix such that:


if u 2e v
>
def
2e
G [u, v] = ⊥
if u6 v


e
where e is any separating edge for u and v.
Since v 2e v for each v ∈ V , G 2e [v, v] = >. An example of a graph with a 2-reachability closure
matrix is given in Figure 1. Note that a 2-reachability closure matrix is not necessarily unique, as
there might be multiple separating edges for a given vertex pair. We define the 2-reachability left
closure GL 2e by replacing any separating edge with first separating edge and the 2-reachability right
closure GR 2e by replacing it with last separating edge.
Note that if there is only one edge separating u and v, then G 2e [u, v] = GL 2e [u, v] = GR 2e [u, v].
Given any 2-reachability closure matrix, one can compute efficiently the 2-reachability left and
right closure matrices. We sketch below the basic idea for the left closure (the right closure being
completely symmetric). Let u and v be any two vertices. If G 2e [u, v] is either > or ⊥, then
GL 2e [u, v] = G 2e [u, v]. Otherwise, let G 2e [u, v] = (x, y): if u 2e x (i.e., if G 2e [u, x] = >)
then (x, y) is the first separating edge for u and v and GL 2e [u, v] = (x, y); otherwise, u6 2e x (i.e.,
G 2e [u, x] 6= >) and GL 2e [u, v] = GL 2e [u, x]. Algorithm 1 gives the pseudo-code for computing the
2-reachability left and right closures GL 2e and GR 2e in a total of O(n2 ) worst-case time.

3

All-pairs 2-reachability in DAGs

In this section, we present our O(nω log n) time algorithm for all-pairs 2-reachability in DAGs. The
high-level idea is to mimic the way Boolean matrix multiplication can be used to compute the
transitive closure of a graph: recursively along a topological order, combine the transitive closure
of the first and the second half of the vertices in a single matrix multiplication. However, while
in transitive closure for each pair (i, j) we have to store only information on whether there is a
path from i to j, for all-pairs 2-reachability this is not enough. First, we describe a path algebra,
used by our algorithm to operate on paths between pairs of vertices in a concise manner. We then
4

Algorithm 1: Closure recovery
Input: N × N matrix IN of 2-reachability closure, type ∈ {left, right}
Output: Matrix OU T of 2-reachability left closure.
1 def recovery(IN, type):
2
OU T ← N × N matrix of undefined
3
for i ← 1 to N do
4
for j ← 1 to N do
5
aux(i, j, IN, OU T, type)
6
return OU T
7 def aux(u, v, IN, OU T, type):
8
if OU T [u][v] is undefined then
9
if IN [u][v] == > or IN [u][v] == ⊥ then
10
OU T [u][v] ← IN [u][v]
11
else
12
(x, y) ← IN [u][v]
13
if type == left then
14
if IN [u][x] == > then
15
OU T [u][v] ← (x, y)
16
else
17
OU T [u][v] ← aux(u, x, IN, OU T, type)
18
else
19
if IN [y][v] == > then
20
OU T [u][v] ← (x, y)
21
else
22
OU T [u][v] ← aux(y, v, IN, OU T, type)
23
return OU T [u][v]
continue with the description of a matrix product-like operation, which is the backbone of our
recursive algorithm. Finally, we show how to implement those operations efficiently using some
binary encoding and decoding at every step of the recursion.
Before introducing our new algorithm, we need some terminology. Let G = (V, E) be a DAG,
and let E1 , E2 be a partition of its edge set E, E = E1 ∪ E2 . We say that a partition is an edge
split if there is no triplet of vertices x, y, z in G such that (x, y) ∈ E2 and (y, z) ∈ E1 simultaneously.
Informally speaking, under such a split, any path in G from a vertex u to a vertex v consists of a
sequence of edges from E1 followed by a sequence of edges from E2 (as a special case, any of those
sequences can be empty). We denote the edge split by G = (V, E1 , E2 ) (See Figure 2). We say that
vertex x in G = (V, E1 , E2 ) is on the left (resp., right) side of the partition if x is adjacent only to
edges in E1 (resp., E2 ). We assume without loss of generality that the vertices of G are given in a
topological ordering v1 , v2 , . . . , vn .

3.1

Algebraic approach

Consider a family of paths P = {P1 , P2 , . . . , P` }, all sharing the same starting and ending vertices u
and v. We would like to distinguish between the following three possibilities: (i) P is empty; (ii) at
least one edge e belongs to every path Pi ∈ P; or (iii) there is no edge that belongs to all paths in
5

E1

v1
P1

P3

Q1

v2
P2

u

E2

v4 Q
4

Pn
v3

Q2

v

Qn
vn

Figure 2: An edge split of a DAG G = (V, E1 , E2 ).
(nonempty) P. To do that, we define the representation repr(P):


if P = ∅
`
U
\
def
repr(P) =
Pi = ∅
if no edge belongs to all Pi


i=1
{e ∈ E : e ∈ Pi , 1 ≤ i ≤ `}
otherwise.
where U denotes the top symbol in the Boolean algebra of sets (i.e., the complement of ∅).
We also define a left representation reprL (P) ∈ E + , where E + = E ∪ {>, ⊥}, as follows:


if P = ∅
⊥
def
reprL (P) = >
if no edge belongs to all Pi


e
such that e ∈ Pi , 1 ≤ i ≤ `, and tail(e) is minimum in the topological order
A right representation reprR (P) ∈ E + is defined symmetrically to reprL (P), by replacing minimum
with maximum. If reprL (P) ∈ E (resp., reprR (P) ∈ E), we say that reprL (P) (resp., reprR (P))
is the first (resp., last) common edge in P. Note that if P is the set of all the paths from u to v,
then repr(P) contains all the information about G 2e [u, v]. Additionally, GL 2e [u, v] = reprL (P) and
GR 2e [u, v] = reprR (P). With a slight abuse of notation we also say that G 2e [u, v] ∈ repr(P).
Observation 3.1. Let G = (V, E1 , E2 ) be an edge split of a DAG, and let u and v be two arbitrary
vertices in G. For 1 ≤ i ≤ n, let Pi = {P ⊆ E1 : P is a path from u to vi }, and Qi = {Q ⊆ E2 :
Q is a path from vi to v} (See Figure
 2) and let S be the family of all paths from u to v. Then:
Tn
repr(S) = i=1 repr(Pi ) ∪ repr(Qi )
A straightforward application of Observation (3.1) yields immediately a polynomial time algorithm
for computing G 2e . However, this algorithm is not very efficient, since the size of repr(P) can be
as large as (n − 1). In the following we will show how to obtain a faster algorithm, by replacing
repr(P) with a suitable combination of reprL (P) and reprR (P).
Lemma 3.2. Let G, Pi , Qi and S be as in Observation 3.1. If vi is such that both u vi in E1 and
vi v in E2 (both Pi 6= ∅ and Qi 6= ∅), then
(a) if reprL (S) = e ∈ E1 and u 6= vi , then reprL (Pi ) = e;
(b) if reprR (S) = e ∈ E2 and vi 6= v, then reprR (Qi ) = e.
6

Proof. We only prove (a), since (b) is completely analogous. Assume by contradiction that reprL (S) =
e ∈ E1 , u 6= vi and vi v in E2 , but reprL (Pi ) = e0 =
6 e. Since reprL (S) = e ∈ E1 , it must be
e ∈ repr(Pi ), as otherwise we would have a path u
vi
v avoiding e. Since e ∈ repr(Pi ) and
reprL (Pi ) = e0 =
6 e, all paths in Pi must go first from u to edge e0 , then to edge e and finally to vi .
However, since reprL (S) = e ∈ E1 , then e is reachable from u by a path avoiding e0 . By definition
of the edge split, this path must be fully contained in E1 , which contradicts the fact that edge e0
precedes e in all paths in Pi .
It is important to note that Lemma 3.2 holds regardless of whether u and v are on the same side
of the partition or not.
Next, we define two operations, denoted as serial and parallel. Although those operations are
formally defined on E + = E ∪ {>, ⊥}, they have a more intuitive interpretation as operations on
path families. We start with the serial operation ⊗. For a, b ∈ E + , we define:
(
(⊥, ⊥)
if a = ⊥ or b = ⊥
def
a⊗b=
(a, b)
otherwise.
def

def

def

We define ⊕ as the parallel operator. Namely, for arbitrary a ∈ E + : a ⊕ ⊥ = a, ⊥ ⊕a = a, a ⊕ > = >,
def
> ⊕ a = >, and otherwise, for e, e0 ∈ E:
(
>
if e 6= e0
def
e ⊕ e0 =
e
if e = e0
def

We extend the definition of ⊕ to operate on elements of E + × E + , as follows: (a1 , b1 ) ⊕ (a2 , b2 ) =
(a1 ⊕ a2 , b1 ⊕ b2 ). Ideally, we want the operator ⊕ either to preserve consistently the first common
edge or to preserve consistently the last common edge, under the union of path families. If for
instance we preserve the first common edge, that means that if P and P 0 are two path families
sharing the same endpoints then we want reprL (P ∪ P 0 ) = reprL (P) ⊕ reprL (P 0 ) to hold. However,
this is not necessarily the case, as for example both P and P 0 could consist of a single path, with
both paths sharing an intermediate edge e0 , but both with two different initial edges, respectively
e1 and e2 . Thus reprL (P) ⊕ reprL (P 0 ) = e1 ⊕ e2 = > while reprL (P ∪ P 0 ) = e0 . As shown in the
following lemma, this is not an issue if the path families considered are exhaustive in taking every
possible path between a pair of vertices.
Lemma 3.3. Let G, Pi , Qi and S be as in Observation 3.1. Then:
Ln
(a)
i=1 (reprL (Pi ) ⊗ reprR (Qi )) = (⊥, ⊥) iff repr(S) = U;
L
(b) if ni=1 (reprL (Pi ) ⊗ reprR (Qi )) = (e1 , >) then repr(S) 3 e1 ;
L
(c) if ni=1 (reprL (Pi ) ⊗ reprR (Qi )) = (>, e2 ) then repr(S) 3 e2 ;
L
(d) if ni=1 (reprL (Pi ) ⊗ reprR (Qi )) = (e1 , e2 ) then repr(S) 3 e1 , e2 ;
Ln
(e)
i=1 (reprL (Pi ) ⊗ reprR (Qi )) = (>, >) iff repr(S) = ∅.
Proof. We proceed with a case analysis:

7

(a) repr(S)
= U iff S = ∅ iff ∀i (Pi = ∅ or Qi = ∅) iff ∀i reprL (Pi ) ⊗ reprR (Qi ) = (⊥, ⊥) iff
Ln
i=1 (reprL (Pi ) ⊗ reprR (Qi )) = (⊥, ⊥).
L
(b) Let ni=1 (reprL (Pi )⊗reprR (Qi )) = (e1 , >). By definition of ⊕, we must have that ∀i (reprL (Pi ) ∈
{e1 , ⊥} ∧ reprR (Qi ) = ⊥) and there must be at least one j such that reprL (Pj ) = e1 and
reprR (Qj ) 6= ⊥. Hence, any path in S must contain e1 .
(c) The proof is similar to (b).
(d) The proof is again similar to (b).
L
(e) If ni=1 (reprL (Pi )⊗reprR (Qi )) 6= (>, >), then by cases (b), (c) or (d) it follows that repr(S) 6= ∅,
clearly a contradiction.
L
To prove the other direction, assume that ni=1 (reprL (Pi )⊗reprR (Qi )) = (>, >) and repr(S) 6= ∅.
From case (a) we know that repr(S) 6= B, and thus there exists an edge e ∈ E such that
e ∈ repr(S). Without loss of generality, assume that e ∈ E1 . Then, it must be reprL (S) = e0
for some edge e0 ∈ E1 . Without loss of generality, assume that v1 , v2 , . . . , vj , are all the vertices
such that simultaneously u vi in E1 , vi v in E2 and u 6= vi (there is at least one such vertex,
since S =
6 ∅ and repr(S) ∩ E1 6= ∅). By Lemma 3.2(a), e0 = reprL (Pi ), 1 ≤ i ≤ j. Thus:
n
M
i=1

(reprL (Pi ) ⊗ reprR (Qi )) =
=

j
M
i=1

0

j
M
i=1

(e , reprR (Qi )) ⊕

0

(e , reprR (Qi )) ⊕

n
M

0

(⊥, ⊥) = (e ,

i=j+1

n
M

(reprL (Pi ) ⊗ reprR (Qi )) =

i=j+1

j
M
i=1

reprR (Qi )) 6= (>, >),

where we have used that (i) if vi = u, then Qi = ∅, as otherwise u v in E2 , with a path avoiding
e ∈ E1 , and (ii) by the choice of j, for i > j, reprL (Pi ) ⊗ reprR (Qi ) = (⊥, ⊥). Thus we have a
contradiction.
We now consider the special case where one side of the partition defined in Observation 3.1
contains only paths of length one. In particular, we say that the edge set E 0 ⊆ E is thin, if there
exists no triplet of vertices x, y, z such that (x, y) ∈ E 0 and (y, z) ∈ E 0 .
Lemma 3.4. Let G, Pi , Qi and S be as in Observation 3.1. Additionally, let E1 be thin. Then
Ln
(a)
i=1 (reprL (Pi ) ⊗ reprR (Qi )) = (⊥, ⊥) iff reprR (S) = ⊥;
Ln
(b) if i=1 (reprL (Pi ) ⊗ reprR (Qi )) = (e1 , >) then reprR (S) = e1 ;
L
(c) if ni=1 (reprL (Pi ) ⊗ reprR (Qi )) = (>, e2 ) then reprR (S) = e2 ;
L
(d) if ni=1 (reprL (Pi ) ⊗ reprR (Qi )) = (e1 , e2 ) then reprR (S) = e2 ;
Ln
(e)
i=1 (reprL (Pi ) ⊗ reprR (Qi )) = (>, >) iff reprR (S) = >.
Proof. Since E1 is thin, we have that for each i: (i) reprL (Pi ) = (u, vi ) iff (u, vi ) ∈ E1 , (ii)
reprL (Pi ) = > iff u = vi and (iii) reprL (Pi ) = ⊥, otherwise. We proceed with a case analysis as in
Lemma 3.3.
8

(a) Since reprR (S) = ⊥ iff repr(S) = U, this case follows immediately from Lemma 3.3(a).
(b) The condition implies that there must be vj such that e1 = (u, vj ) and vj 2e v in E2 . Additionally,
for all i =
6 j such that vi 6= u, either (u, vi ) 6∈ E1 or vi 6 v in E2 , and for vi = u there is vi 6 v in
E2 . It follows that every path in G from u to v must go through vertex vj , and since E1 is thin,
this makes e1 the separating edge. Since vj 2e v, edge e1 is the only possible separating edge
for u and v. Hence, reprR (S) = e1 .
(c) The condition implies that for any 1 ≤ j ≤ n, exactly one of the constraints is satisfied: (i) u vj
in E1 (equivalently vj = u or (u, vj ) ∈ E1 ) and reprR (Qj ) = e2 , (ii) u6 vj in E1 (that is, vj 6= u
and (u, vj ) 6∈ E1 ) or (iii) vj 6 v in E2 . Additionally, unless there exists a j such that vj = u (which
would mean u 2e vj ), the first constraint is satisfied for
least two distinct values of j since
Lat
n
the conditions (ii) and (iii) are not sufficient to satisfy i=1 (reprL (Pi ) ⊗ reprR (Qi )) = (>, e2 ).
It follows that reprR (S) = e2 .
(d) The condition implies that for exactly one j, there exists an edge e1 = (u, vj ) and vj v in
E2 , and reprR (Qj ) = e2 . Additionally, for every i 6= j, either u6 vj in E1 (that is, vj 6= u and
(u, vj ) 6∈ E1 ) or vj 6 v in E2 (since otherwise there would be a path avoiding e1 ). Similarly to
case (c), it follows that reprR (S) = e2 .
(e) Since reprR (S) = > iff repr(S) = ∅, this case follows immediately from Lemma 3.3(e).
One could prove a symmetric version of Lemma 3.4, with E2 being thin. However, in the
remainder of the paper we stick with Lemma 3.4: namely, we choose a partition with a thin left side
and thus break case (d) of Lemma 3.4 in favor of the rightmost edge (instead of the leftmost edge, as
it would be in the symmetric version). Consistently, we define the following projection operator π:
def
def
def
π(⊥, ⊥) = ⊥, π(>, >) = >, π(e0 , e) = π(>, e) = π(e, >) = e. With this new terminology, Lemma 3.3
and Lemma 3.4 can be simply restated as follows:
Corollary 3.5. Let G, Pi , Qi and S be as in Observation 3.1. Then
L
(i) π( ni=1 (reprL (Pi ) ⊗ reprR (Qi ))) = > iff repr(S) = ∅,
L
(ii) π( ni=1 (reprL (Pi ) ⊗ reprR (Qi ))) = ⊥ iff repr(S) = U, and
L
(iii) π( ni=1 (reprL (Pi ) ⊗ reprR (Qi ))) ∈ repr(S) otherwise.
Corollary 3.6. Let G, Pi , Qi and S be as in Observation 3.1, and let E1 be thin. Then π(
reprR (Qi ))) = reprR (S).

Ln

i=1 (reprL (Pi )⊗

define a path-based matrix product based on the previously defined
Matrix product. Now weL
def
operators: (A ◦ B)[i, j] = π
k A[i, k] ⊗ B[k, j] . Throughout, we assume that the vertices of G
are sorted according to a topological ordering. In the following lemma, B represents a thin set of
edges (i.e., the set of edges from a subset of vertices to another disjoint subset of vertices).


A B
be the adjacency matrix of a DAG G = (V, E), where A, B and C are
Lemma 3.7. Let
0 C
respectively k × k, k × (n − k) and (n − k) × (n − k) submatrices. If B is the matrix containing ⊥
for every 0 in B and the appropriate e ∈ E for every 1 in B, then:
 2e

AL
AL 2e ◦ (B ◦ CR 2e )
⊥
CR 2e
9

is a 2-reachability closure of G (not necessarily unique).
Proof. Let V = {v1 , v2 , . . . , vn } be the vertex set in order of rows and columns of the input matrix,
and let V1 = {v1 , v2 , . . . , vk } and V2 = {vk+1 , . . . , vn }. Matrices A, B and C correspond respectively
to all edges from V1 to V1 , to all edges from V1 to V2 and to all edges from V2 to V2 . We refer to the
edge sets represented by those matrices as EA , EB and EC . As a consequence of the fact that there
are no edges from V2 to V1 , any path from V1 to V1 can use only edges from EA , and any path from
V2 to V2 can use only edges from EC . Thus:


 2e

A 0 2e
AL
⊥
(V, EA )L 2e =
=
,
0 0 L
⊥
I



0 B 2e
I B
=
=
,
0 0 L
⊥ I




0 0 2e
I
⊥
=
=
,
0 C R
⊥ CR 2e


(V, EB )L
(V, EC )R 2e
where

2e


> ⊥ ···
⊥ > · · ·
def 
I =. . .
..
 .. ..
⊥ ⊥ ···


⊥
⊥

.. 
.
>

By Corollary 3.6 (since EB is thin) and by definition of path-based matrix product:

 
 

I B
I
⊥
I B ◦ CR 2e
(V, EB ∪ EC )R 2e = (V, EB )L 2e ◦ (V, EC )R 2e =
◦
=
.
⊥ I
⊥ CR 2e
⊥
CR 2e
Finally, by Corollary 3.5:
(V, EA )L

2e

◦ (V, EB ∪ EC )R

2e

 2e
AL
=
⊥

 
  2e
I B ◦ CR 2e
AL
⊥
◦
=
⊥
I
⊥
CR 2e

AL 2e ◦ (B ◦ CR 2e )
CR 2e



is a 2-reachability closure of G.
By Lemma 3.7, the 2-reachability closure can be computed by performing path-based matrix
products on the left and right 2-reachability closures of smaller matrices. This gives immediately a
recursive algorithm for computing the 2-reachability closure: indeed, as already shown in Section 2,
one can compute the left and right 2-reachability closures in O(n2 ) time from any 2-reachability
closure. In the next section we show how to implement this recursion efficiently by describing how
to compute efficiently path-based matrix products.

3.2

Encoding and decoding for Boolean matrix product

We start this section by showing how to efficiently compute path-based matrix products using Boolean
matrix multiplications. The first step is to encode each entry of the matrix as a bitword of length 8k
where k = dlog2 (n + 1)e. We use Boolean matrix multiplication of matrices of bitwords, with bitwise
AND/OR operations, denoted respectively with symbols ∧ and ∨. Our bitword length is O(log n),
10

Algorithm 2: Left- and right-side encoding
Input: Matrix IN of dimension N × M with elements in E + ; type ∈ {left,right}.
Output: Matrix OU T of dimension N × M consisting of bitwords.
1 def encode(IN, type):
2
forall IN [i][j] do
3
if IN [i][j] == ⊥ then
4
OU T [i][j] ← {0}8k
5
else if IN [i][j] == > then
6
OU T [i][j] ← {1}8k
7
else
. IN [i][j] ∈ E
8
(x, y) ← IN [i][j]
9
b1 b2 . . . bk ← binary encoding of x
10
c1 c2 . . . ck ← binary encoding of y
11
if type == left then
12
OU T [i][j] ← b1 b2 . . . bk c1 c2 . . . ck b1 b2 . . . bk c1 c2 . . . ck {1}4k
13
else
14
OU T [i][j] ← {1}4k b1 b2 . . . bk c1 c2 . . . ck b1 b2 . . . bk c1 c2 . . . ck
15
return OUT
so matrix multiplication takes O(nω log n) time by performing Boolean matrix multiplication for
each coordinate separately.
We make use of the fact that after each multiplication we can afford a post-processing phase,
where we perform actions which guarantee that the resulting bitwords represent a valid 2-reachability
closure.
First, we note that when encoding a specific matrix, we know whether it is used as a left-side
or as a right-side component of multiplication. The main idea is to encode left-side and right-side
⊥ as {0}8k , left-side and right-side > as {1}8k . For any other value, append {1}4k as a prefix or
suffix (depending on whether it is used as a left-side or right-side component), to the encoding of an
edge. The encoding of an edge is a simple 1-superimposed code: the concatenation of the edge ID
and the complement of the edge ID. To be more precise, whenever a bitword represents an edge e
in a left-closure, then it is of the form IDe IDe {1}4k ; whenever a bitword represents an edge e in a
right-closure, then it is of the form {1}4k IDe IDe , where w denotes the complement of bitword w.
The implementation of this encoding is given in Algorithm 2.
The serial operator ⊗ is implemented by coordinate-wise AND over two bitwords. Recall that
the operator ⊗ always has as its first (left) operand an element from a left-closure matrix and as its
second (right) operand an element from a right-closure. It is easy to verify that the result of AND is
a concatenation of two bitwords of length 4k encoding either ⊥, > or e ∈ E. We observe that ⊗ is
calculated properly in all cases: (let e, e1 , e2 ∈ E, e1 6= e2 )
1. e ⊗ > = (e, >) since IDe IDe {1}4k ∧ {1}8k = IDe IDe {1}4k
2. > ⊗ e = (e, >) since {1}8k ∧ {1}4k IDe IDe = {1}4k IDe IDe
3. e1 ⊗ e2 = (e1 , e2 ) since IDe1 IDe1 {1}4k ∧ {1}4k IDe2 IDe2 = IDe1 IDe1 IDe2 IDe2
4. e ⊗ ⊥ = > ⊗ ⊥ = ⊥ ⊗ ⊥ = ⊥ ⊗ e = ⊥ ⊗ > = (⊥, ⊥) since {0, 1}8k ∧ {0}8k = {0}8k
11

Algorithm 3: Decoding
Input: Matrix IN of dimension N × M consisting of bitwords.
Output: Matrix OU T of dimension N × M consisting of elements in E + .
1 def decode(IN ):
2
forall IN [i][j] do
3
b1 b2 . . . b8k ← IN [i][j]
4
if b1 b2 . . . b8k == {0}8k then
5
OU T [i][j] ← ⊥
6
else if b4k+1 b4k+2 . . . b6k == b6k+1 b6k+2 . . . b8k then
7
x ← binary decoding of b4k+1 b4k+2 . . . b5k
8
y ← binary decoding of b5k+1 b5k+2 . . . b6k
9
OU T [i][j] ← (x, y)
10
else if b1 b2 . . . b2k == b2k+1 b2k+2 . . . b4k then
11
x ← binary decoding of b1 b2 . . . bk
12
y ← binary decoding of bk+1 bk+2 . . . b2k
13
OU T [i][j] ← (x, y)
14
else
15
OU T [i][j] ← >
16
return OUT
5. > ⊗ > = (>, >) since {1}8k ∧ {1}8k = {1}8k
The parallel operator ⊕ is implemented as coordinate-wise OR over bitwords of length 8k.
Note that all bitwords can be binary representations of pairs of elements in E + of the form
(e1 , e2 ), (e1 , >), (>, e2 ), (⊥, ⊥), (>, >), since only those forms appear as a result of an ⊗ operation.
Recall that ⊕ satisfies (a1 , b1 ) ⊕ (a2 , b2 ) = (a1 ⊕ a2 , b1 ⊕ b2 ), thus w.l.o.g. it is enough to verify the
correctness of the implementation over the first 4k bits of encoding. Observe that all cases, except
when both bitwords include encoded edges, are managed correctly by the execution of coordinate-wise
OR: (let e ∈ E)
1. ⊥ ⊕ ⊥ = ⊥ since {0}4k ∨ {0}4k = {0}4k
2. ⊥ ⊕ e = e ⊕ ⊥ = e since IDe IDe ∨ {0}4k = IDe IDe
3. ⊥ ⊕ > = > ⊕ ⊥ = > since {1}4k ∨ {0}4k = {1}4k
4. e ⊕ > = > ⊕ e = > since IDe IDe ∨ {1}4k = {1}4k
We are only left to take care of operations of the form e1 ⊕ e2 for e1 , e2 ∈ E. According to the
definition of the parallel operator ⊕, we would like e1 ⊕ e2 = e ∈ E iff e1 = e2 = e and otherwise
e1 ⊕ e2 = >. This special case is handled by the fact that we encode edges using 1-superimposed
codes. That is, the binary representation of IDe has the property that IDe [1 .. 2k] = IDe [2k + 1 .. 4k].
Moreover, the coordinate-wise OR of two encodings of edges, that is X = IDe1 ∨ IDe2 , has this
property iff e1 = e2 .
Thus in order to successfully decode the result of chained ⊕ from coordinate-wise OR, we need
to distinguish the following cases (our result is encoded as X = X[1 .. 2k]X[2k + 1 .. 4k]):
1. X = {0}4k , then the result is ⊥,
12

Algorithm 4: Path-based matrix product
Input: Matrices A and B of compatible dimension.
Output: Matrix being a path-based product of inputs.
1 def mul(A, B):
2
return decode(encode(A, left) · encode(B, right))
. here · denotes coordinate-wise Boolean matrix multiplication
2. X[1 .. 2k] = X[2k + 1 .. 4k], then X is the encoding of the resulting edge,
3. otherwise the result is >.
With all the tools and notation from above, theWpath-based matrix product over bitwords can be equiva- 
def
lently stated as (AL 2e ◦BR 2e )[i, j] = decode k encode(AL 2e [i, k], left) ∧ encode(BR 2e [k, j], right) ,
where the pseudocode for decode is provided in Algorithm 3.
To compute the entries of the final path-based matrix product (before the execution of decode) it
suffices to compute the bitwise Boolean matrix product of appropriate bitword matrices. That is, we
apply encode to AL 2e and BR 2e , then we execute the Boolean matrix product for each coordinate
separately, concatenate the coordinates of the resulting Boolean matrices into a matrix of bitwords,
and finally execute the decode operation from Algorithm 3. This is illustrated in Algorithm 4.
All the tools developed in this section allow us to compute the 2-reachability closure for DAGs.
Our recursive algorithm follows closely Lemma 3.7, and its implementation in pseudocode is given
as Algorithm 5. Since we implemented the right-side version of the projection, we have only to be
careful to perform first the right multiplication before the left multiplication.
Lemma 3.8. Given a DAG with n vertices, Algorithm 5 computes its 2-reachability closure in time
O(nω log n).
Proof. Algorithm 4 computes the path-based matrix product of matrices with every dimension
bounded by n, if the initial graph size was n0 , in time O(nω log n0 ), as it needs to compute O(log n0 )
Boolean matrix products, one for each coordinate of the stored bitwords. Closures are computed in
time O(n2 ). The recursion that captures the runtime of Algorithm 5 is thus given by the formula
T (n) = T (bn/2c) + T (dn/2e) + O(nω log n0 ) which is satisfied by setting T (n) = O(nω log n0 ). The
bound follows.

4

All-pairs 2-reachability in strongly connected graphs

In this section we focus on strongly connected graphs. In this case reachability is simple: for any
pair of vertices (u, v) ∈ V × V we have u v in G. But in case that u6 2e v in G, finding a separating
edge that appears in all paths from u to v in G can still be a challenge. We show that we can report
such an edge in constant time after O(nω ) preprocessing. The main result of this section is the
following theorem.
Theorem 4.1. The 2-reachability closure of a strongly connected graph can be computed in time
O(nω ).
Our construction is based on the notion of auxiliary graph and it will be given in Section 4.3.
A detailed implementation will be provided in Algorithm 6. Its running time will be analyzed in
Lemma 4.7 and its correctness hinges on Lemma 4.9.
13

Algorithm 5: 2-reachability closure for DAGs
Input: Matrix G of dimension N × N , G is a DAG with topological order 1, 2, . . . , n.
Output: 2-reachability closure of G.
1 def closureDAG(G):
2
if N == 1 then
 
3
return >
4
N 0 ← bN/2c
5
A ← G[1 .. N 0 ][1 .. N 0 ]
6
B ← G[1 .. N 0 ][(N 0 + 1) .. N ], 0’s replaced with ⊥ and 1’s with edge labels
7
C ← G[(N 0 + 1) .. N ][(N 0 + 1) .. N ]
8
A0 ← recovery(closureDAG(A), left)
9
C 0 ← recovery(closureDAG(C), right)
 0

A mul(A0 , mul(B, C 0 ))
10
return
0
C0

4.1

Reduction to two single-source problems

Let G = (V, E) be a strongly connected digraph. Let s be a fixed but arbitrary vertex of G. The
proof of the following lemma is immediate.
Lemma 4.2. For any pair of vertices u and v: If there is an edge e ∈ E(G) such that u6 v in G \ e,
then either u6 s in G \ e or s6 v in G \ e.
Let Pu,s be the family of all paths from u to s and let Ps,v be the family of all paths from s to
v. We denote by eu the first edge on all paths in Pu,s , and by ev the last edge on all paths in Ps,v .
Note that there might be no edge that is on all paths of Pu,s : in this case we say that eu does not
exist. If there are several edges on all paths in Pu,s , then they are totally ordered, so it is clear which
is the first edge (similarly for ev and Ps,v ). We now show that in order to search for a separation
witness for (u, v), it suffices to focus on eu and ev .
Lemma 4.3. If there is some e such that u6 v in G \ e, then at least one of the following statements
is true:
• eu exists and u6 v in G \ eu .
• ev exists and u6 v in G \ ev .
Proof. If e = eu or e = ev , the claim is trivial. Otherwise, by Lemma 4.2, we know that u6 s or
s6 v in G \ e. Let us assume that u6 s (See Figure 3). So e lies not only on any path from u to v
but also on any path from u to s. As eu is the first common edge of every path from u to s, eu also
lies on every path from u to e. As all paths from u to v have to go through e, they also have to
go through eu and hence u6 v in G \ eu . If s6 v in G \ e, we can show that u6 v in G \ ev by the
same extremality argument for ev .
Hence, in order to check whether there is an edge that separates u from v in G, it suffices to
look at the reachability information in G \ eu (a graph which does not depend on u) and at the
reachability information in G \ ev (a graph which does not depend on v). Unfortunately, this is not
enough to derive an efficient algorithm, since we would have still to look at as many as 2n different
14

s
u

eu

ev

e
v

Figure 3: Illustration of the first case of Lemma 4.3.
graphs (as we explain later, and as it was first shown in [13], there can be at most 2n − 2 edges
whose removal can affect the strong connectivity of the graph). As a result, computing the transitive
closures of all those graphs would require O(nω+1 ) time. The key insight to reduce the running
time to O(nω ) is to construct an auxiliary graph H, whose reachability is identical to G \ ev for any
query pair (u, v), and a second auxiliary graph H 0 whose reachability is identical to G \ eu for any
query pair (u, v). Note that the edge that is missing from the graph depends always on one of the
two endpoints of the reachability query. As a consequence, we have to consider only n2 and not n3
different queries for H and H 0 .

4.2

Strong bridges and dominator tree decomposition

Before we construct these auxiliary graphs, we need some more terminology and prior results.
Flow graphs, dominators, and bridges. A flow graph Gs = (V, E, s) is a digraph with a
R
distinguished start vertex s. We denote by GR
s = (V, E , s) the reverse flow graph of Gs ; the graph
resulted by reversing the direction of all edges e ∈ E. Vertex u is a dominator of a vertex v (u
dominates v) if every path from s to v in Gs contains u; u is a proper dominator of v if u dominates
v and u =
6 v. The dominator relation is reflexive and transitive. Its transitive reduction is a rooted
tree, the dominator tree D: u dominates v if and only if u is an ancestor of v in D, see Figure 4 and
Figure 5 for examples. If v 6= s, the parent of v in D, denoted by d(v), is the immediate dominator
of v: it is the unique proper dominator of v that is dominated by all proper dominators of v. For
any vertex v, we let D(v) denote the set of descendants of v in D, i.e., the vertices dominated by
v. Lengauer and Tarjan [17] presented an algorithm for computing dominators in O(mα(m, n))
time for a flow graph with n vertices and m edges, where α is a functional inverse of Ackermann’s
function [22]. Dominators can be computed in linear time [2, 4, 9]. An edge (x, y) is a bridge of the
flow graph Gs if all paths from s to y include (x, y).
Strong bridges. Let G = (V, E) be a strongly connected digraph. An edge e of G is a strong
bridge if G \ e is no longer strongly connected. Let s be an arbitrary start vertex of G. Since G is
strongly connected, all vertices are reachable from s and reach s, so we can view both G and GR as
flow graphs with start vertex s, denoted respectively by Gs and GR
s.
Property 4.4. ([13]) Let s be an arbitrary start vertex of G. An edge e = (x, y) is a strong bridge
of G if and only if it is a bridge of Gs or a bridge of GR
s (or both).
As a consequence of Property 4.4, all the strong bridges of the digraph G can be obtained from
the bridges of the flow graphs Gs and GR
s , and thus there can be at most (2n − 2) strong bridges in
a digraph G. Using the linear time algorithms for computing dominators, we can thus compute all
strong bridges of G in time O(m + n) ⊆ O(nω ). We use the following lemma from [10] that holds
for a flow graph Gs of a strongly connected digraph G.
15

Gs
s
D
s

b

a
c

a

c

b

d
d
e

f

e

f

h

g
g
h

Figure 4: A flow graph and its dominator tree. Edges marked in red are bridges.
Lemma 4.5. ([10]) Let G be a strongly connected digraph and let (x, y) be a strong bridge of G.
Also, let D and DR be the dominator trees of the corresponding flow graphs Gs and GR
s , respectively,
for an arbitrary start vertex s.
(a) Suppose x = d(y). Let w be any vertex that is not a descendant of y in D. Then there is a path
from w to x in G that does not contain any proper descendant of y in D. Moreover, all simple
paths in G from w to any descendant of y in D must contain the edge (d(y), y).
(b) Suppose y = dR (x). Let w be any vertex that is not a descendant of x in DR . Then there is a
path from x to w in G that does not contain any proper descendant of x in DR . Moreover, all
simple paths in G from any descendant of x in DR to w must contain the edge (x, dR (x)).
Bridge decomposition. After deleting from the dominator trees D and DR respectively the
R
R
bridges of Gs and GR
s , we obtain the bridge decomposition of D and D into forests D and D .
R
R
Throughout this section, we denote by Tv (resp., Tv ) the tree in D (resp., D ) containing vertex v,
and by rv (resp., rvR ) the root of Tv (resp., TvR ). Given a digraph G = (V, E), and a set of vertices
S ⊆ V , we denote by G[S] the subgraph induced by S. In particular, G[D(r)] denotes the subgraph
induced by the descendants of vertex r in D.

4.3

Overview of the algorithm and construction of auxiliary graphs

The high-level idea of our algorithm is to compute two auxiliary graphs H and H 0 from G and GR ,
respectively, with the following property: Given two vertices u and v, we have that u 2e v in G if
and only u v in H and v u in H 0 . To construct the auxiliary graphs H and H 0 , we use the bridge
decompositions of D and DR , respectively.
The two extremal edges eu and ev , defined in Section 4.1, can be also defined in terms of the bridge
decompositions. In particular, ev is the bridge entering the tree Tv of the bridge decomposition of D,
so ev = (d(rv ), rv ), and eu is the reverse bridge entering the tree DuR of the bridge decomposition
of DR , so eu = (ruR , dR (ruR )). Hence if there exists a path from u to v avoiding each of the strong
bridges ev and eu , then u 2e v in G. By Lemma 4.3, it is enough if H models the reachability of
G \ ev and H 0 the reachability of G \ eu . So H is responsible for answering whether u has a path to
16

GR
s
s
b

a

DR
s

c
a

d

d

e

b

f

e

c

g

h
f

g
h

Figure 5: A reverse flow graph and its dominator tree. Edges marked in red are bridges.
v avoiding ev , while H 0 is responsible for answering whether u has a path to v avoiding eu . Then, if
any of the reachability queries in H and H 0 returns false, we immediately have an edge that appears
in all paths from u to v.
We next show to compute the auxiliary graphs H and H 0 in O(n2 ) time. In particular, the
auxiliary graph H = (V, E 0 ) of the flow graph Gs = (V, E, s) is constructed as follows. Initially,
E 0 = E \ BR, where BR is the set of bridges of Gs . For all bridges (p, q) of Gs do the following:
For each edge (x, y) ∈ E such that x ∈ D(q), y ∈
/ D(q), we add the edge (p, y) in E 0 , i.e., we set
0
0
E = E ∪ (p, y). A detailed implementation is provided in Algorithm 6. Together with graph
H, the algorithm outputs an array of edges (“witnesses”) W , such that for each vertex v 6= s,
W [v] = (d(rv ), rv ) is a candidate separating edge for v and any other vertex. The computation of
H 0 is completely analogous.
Once H and H 0 are computed, their transitive closure can be computed in O(nω ) time, after
which reachability queries can be answered in constant time. Thus, we can preprocess a strongly
connected digraph G in total time O(nω ) and answer 2-reachability queries in constant time, as
claimed by Theorem 4.1.
Definition 4.6 (Auxiliary graph construction). The auxiliary graph H = (V, E 0 ) of the flow graph
Gs = (V, E, s) is constructed as follows. Initially, E 0 = E \ BR, where BR is the set of bridges of Gs .
For all bridges (p, q) of Gs do the following: For each edge (x, y) ∈ E such that x ∈ D(q), y ∈
/ D(q),
0
0
0
we add the edge (p, y) in E , i.e., we set E = E ∪ (p, y).
Lemma 4.7. The auxiliary graph H can be computed in O(n2 ) time and space.
Proof. For each root r of a tree Tr ∈ D, we maintain a set R(r) ⊆ V , initially set to ∅. The value
R(r) contains all such endpoints y of edge (x, y) such that x ∈ D(r) and y ∈
/ D(r). We process the
trees of the bridge decomposition in a bottom-up order of their roots. For each root r that we visit
we compute R(r) in the following tree steps. First, for each bridge (p, q) of Gs such that p ∈ Tr ,
we update R(r) by setting R(r) = R(r) ∪ R(q). Second, for every edge (x, y) such that x ∈ Tr we
insert y into R(r). Finally, we remove all D(r), that is R(r) = R(r) \ D(r). We execute this final
step since we are only interested whether there is an edge (x, y) such that x ∈ D(r) and y ∈
/ D(r).
Clearly, after these steps the set R(r) contains only the desired endpoints.
17

Algorithm 6: 2-reachability closure in strongly connected graphs
Input: Strongly connected graph G on N vertices.
Output: 2-reachability closure of G.
1 def closureSCC(G):
2
s ← arbitrary vertex of G
3
H, W ← auxiliaryGraph(G, s)
4
H 0 , W 0 ← auxiliaryGraph(GR , s)
5
OU T ← N × N matrix
6
forall OU T [i][j] do
7
if (i, j) 6∈ H then
8
OU T [i][j] ← W [j]
9
else if (j, i) 6∈ H 0 then
10
OU T [i][j] ← W 0 [i]R
11
else
12
OU T [i][j] ← >
13
return OUT
14 def auxiliaryGraph(G, s):
15
H←G
16
W, R ← arrays of size N
17
D ← dominator tree of Gs
18
for tree T , S
rooted
at r, in bottom-up order of bridge decomposition of D do

0
0
19
R[r] ←
R[r ]S: d(r
. r0 is root of children component of T
 ) 0∈ V (T0)
20
D[r] ← V (T ) ∪
D[r ] : d(r ) ∈ V (T )
21
for (x, y) ∈ V (T ) × V (G) do
22
if (x, y) ∈ G then
23
R[r] ← R[r] ∪ {y}
24
R[r] ← R[r] \ D[r]
25
if s 6∈ T then
26
p ← d(r)
. (p, r) is a bridge connecting parent of T to T
27
for y ∈ R[r] do
28
H ← H ∪ (p, y)
29
for x ∈ V (T ) do
30
W [x] ← (p, r)
31
H ← H \ (p, r)
32
return transitiveClosure(H),W

18

Gs

H

GR
s

H0

s

s

s

s

b

a

b

a

c

c

f

e

h

f

e

g

g

d

d
f

e

c

c

d

d

b

a

b

a

g

g
h

f

e

h

h

Figure 6: Auxiliary graphs H and H 0 which are derived from Gs and GR
s , respectively. The deleted
edges, the bridges of Gs and GR
,
are
shown
in
red,
the
newly
added
edges
are shown in blue. The
s
R
blue edges are drawn along the green edges from Gs and Gs which are the reason for their insertion.
Here we see, that for example b is 2-reachable from e, since there are two (edge and vertex) disjoint
paths (e, g, c, d, b) and (e, f, h, s, b) in G. In H, e reaches b through the path (e, c, b), and in H 0 , b
reaches e through the path (b, s, h, e). We also see, that edge (c, d) separates a and f in G, and even
though f reaches a in H 0 through the path (f, d, c, a), a does not reach f in H. To illustrate why
both H and H 0 are relevant in Lemma 4.9, consider the following example: vertex c is unreachable
from b in G \ (b, c), which we also detect as there is no c-b path in H 0 (even though there is a b-c
path in H).
Note that we actually wish to insert edges to d(r) for each root r of a tree on the bridge
decomposition. Therefore, after computing for each root r its set R(r), we insert to H an edge
(d(r), y) for every y ∈ R(r) (notice that the outgoing edges of d(r) in G, except (d(r), r), are also
outgoing edges of d(r) in H). Overall, by representing sets as bitmasks, all the R(r) sets can be
computed in O(n2 ) time. We spend O(n2 ) time in the third step, since we visit each vertex at most
one. Since we traverse every edge only once, the second step takes O(n + m) in total. The bound
follows.
Lemma 4.8. For all w ∈ V , no edge (x, y) ∈ E(H) exists with x ∈
/ D(rw ) and y ∈ D(rw ).
Proof. Assume, by contradiction, that there is an edge (x, y) ∈ E(H) such that x ∈
/ D(rw ) and
y ∈ D(rw ). Since (d(rw ), rw ) is a strong bridge in Gs , (x, y) does not exist in G (by Lemma 4.5).
Hence, by construction, there is an edge (z, y) ∈ E(G) where z ∈ D(x)\x and y ∈
/ D(x). Therefore, x
cannot be an ancestor of w in D, which implies z ∈
/ D(rw ) and z =
6 d(rw ) since D(z)∩D(rw ) = ∅. This
is a contradiction, since (z, y), where z ∈
/ D(rw ) and y ∈ D(rw ), cannot exist in G by Lemma 4.5.
To show the correctness of our approach, we consider queries where we are given an ordered pair
of vertices (u, v), and we wish to return whether there exists an edge e such that u6 v in G \ e. We
can answer this query in constant time by answering the queries u v in H and v u in H 0 . Given
Lemma 4.3, it is sufficient to prove the following:
Lemma 4.9. The auxiliary graphs H and H 0 satisfy these two conditions:
• If ev exists, then u v in G \ ev if and only if u v in H.
• If eu exists, then u v in G \ eu if and only if v
19

u in H 0 .

We prove the lemma in two separate steps, one for each direction of the two equivalences.
Lemma 4.10. If u v in H then u v in G \ ev (and if v

u in H 0 then u v in G \ eu ).

Proof. By Lemma 4.8, there are no edges incoming into D(rv ) in H. So for a path P from u to v in
H to exist, u must lie in D(rv ) and P must lie within H[D(rv )]. Clearly, if P contains only edges
from E(G[D(rv )]), then P is also a valid path from u to v in G[D(rv )] and thus also in G \ ev (recall
that ev = (d(rv ), rv )) and we are done.
Otherwise, we iteratively substitute auxiliary edges of P , with paths in G \ ev , so that in the end,
P is fully contained within G \ ev . Let e∗ = (x∗ , y ∗ ) be the first edge of P such that e∗ ∈
/ E(G[D(rv )]),
i.e. an auxiliary edge of H. By eo = (xo , y o ), we denote the original edge for which we inserted e∗
into H. Then xo ∈ D(x∗ ) \ x∗ and y ∗ = y o . Since all paths from s to xo contain x∗ , and all simple
paths from x∗ to xo avoid vertices from V \ D(rv ) (otherwise, if all paths contained such a vertex
w then s would have a path to xo in G avoiding x∗ by Lemma 4.5), it follows that x∗ has a path
Px∗ xo to xo in G[D(rv )]. If we now replace e∗ in P by Px∗ xo · eo , then P contains a path from u to
y ∗ containing only edges in G \ ev . We repeat this argument as long as P contains auxiliary edges
and get a path from u to v in G \ ev .
The statement for H 0 and G \ eu can be shown with completely analogous arguments.
Lemma 4.11. If u v in G \ ev then u v in H (and if u v in G \ eu then v

u in H 0 ).

Proof. By Lemma 4.5 (a), ev is the only edge in G entering D(rv ). So any path P from u to v in
G \ ev can only use edges in E(G[D(rv )]). If P only contains edges in H, we are done. Otherwise,
let e∗ = (x∗ , y ∗ ) be the first edge of P that is in E(G[D(rv )]) but not in H, hence e∗ is a bridge of
Gs . Let z ∗ be the first vertex on P after e∗ that is not a descendant of y ∗ in D. Such a vertex z ∗
exists since P ends at v but v is not a descendant of y ∗ (recall that e∗ is a bridge and lies within
G[D(rv )]). Thus, we can replace the subpath of P between e∗ and z ∗ (including e∗ ) by the edge
(x∗ , z ∗ ) which is an auxiliary edge of H, by the definition of H. We repeat this argument as long as
P contains bridges of Gs and get a path from u to v in H.
The statement for G \ eu and H 0 can be shown with completely analogous arguments.

5

All-pairs 2-reachability in general graphs

In this section, we show how to compute the 2-reachability of a general digraph by suitably combining
the previous algorithms for DAGs and for strongly connected digraphs. First, note that the 2reachability closure of a strongly connected graph G can be constructed as follows: G 2e [i, j] = >
if i has two edge-disjoint paths to j and G 2e [i, j] ∈ E if there is an edge e ∈ E such that i6 j in
G \ e. No entry of G 2e contains ⊥ since G is strongly connected. After O(nω ) time preprocessing
all the above queries can be answered in constant time. Therefore, the 2-reachability closure can be
computed in O(nω ) time.
Let G be a general digraph. The condensation of G is the DAG resulting after the contraction of
every strongly connected component of G into a single vertex. We assume, without loss of generality,
that the vertices are ordered as follows: The vertices in the same strongly connected component of
G appear consecutively in an arbitrary order, and the strongly connected components are ordered
with respect to the topological ordering of the condensation of G. Moreover, we assume that we
have access to a function stronglyConnected(u, v) that answers whether the vertices u and v are
strongly connected.
20

Algorithm 7: 2-reachability closure in general graphs
Input: Matrix G of dimension N × N , with vertices ordered w.r.t. some fixed topological
order of strongly connected components
Output: 2-reachability closure of G.
1 def closure(G):
2
if N == 1 then
 
3
return >
4
else if ∀i, j ∈ {1, . . . , N } stronglyConnected(i, j) == true then
5
return closureSCC(G)
6
I = {i : 1 ≤ i < N, stronglyConnected(i, i + 1) == false}
7
N 0 ← arg mini∈I {|i − N/2|}
8
A ← G[1 .. N 0 ][1 .. N 0 ]
9
B ← G[1 .. N 0 ][(N 0 + 1) .. N ], 0 replaced with ⊥ and 1 with edge labels
10
C ← G[(N 0 + 1) .. N ][(N 0 + 1) .. N ]
11
A0 ← recovery(closure(A), left)
12
C 0 ← recovery(closure(C), right)

 0
A mul(A0 , mul(B, C 0 ))
13
return
0
C0
The key insight is that every idea presented in Section 3 never truly used the fact that the input
graph is a DAG, just the properties of an edge split, that is finding edge partition into two sets so
that no vertex has incoming edge from second set and outgoing edge from first set simultaneously. If
we are able to extend the definition of an edge split to a general graph in a way highlighted above,
and the definitions of repr(), reprR () and reprL (), then all of the results from Section 3 carry over
to a general graph G. Note that given arbitrary path family P, reprL (P) and reprR (P) might be
ill-defined, since paths in an arbitrary path family might not share the order of common edges.
However, we are only using this notation for path families containing exactly all of paths connecting
a given pair of vertices in the graph: for such families, the order of common edges is shared.
The high-level idea behind our approach is to extend the 2-reachability closure algorithm for
DAGs, as follows. At each recursive call, the algorithm attempts to find a balanced separation of
the set of vertices, with respect to their fixed precomputed order, into two sets such that there is
no pair across the two sets that is strongly connected. If such a balanced separation can be found,
then the instance is (roughly) equally divided into two instances. Otherwise, if there is no balanced
separation of the set of vertices into two subsets, then one of the following properties holds: (i) the
larger instance is a strongly connected component, or (ii) the recursive call on the larger instance
separates a large strongly connected component, on which we can compute the 2-reachability closure
in O(nω ) time. We provide pseudocode for this in Algorithm 7.
Theorem 5.1. Algorithm 7 computes 2-reachability closure of graph on n vertices in time O(nω log n).
Proof. The algorithm correctness follows from the correctness of Algorithm 5 and the fact that Algorithm 7 separates the input matrix G with dimensions N ×N into submatrices A = G[1 .. N 0 ][1 .. N 0 ],
B = G[1 .. N 0 ][(N 0 + 1) .. N ] and C = G[(N 0 + 1) .. N ][(N 0 + 1) .. N ], and such that ∀i ∈ [1, N 0 ], j ∈
[N 0 + 1, N ] : G[j, i] = 0 as required by Lemma 3.7. Now we show that Algorithm 7 has the same
asymptotic running time as Algorithm 5.
The recurrence that provides the running time is the following (we denote by N0 the size of the
21

original graph)
T (N ) = T (min{N 0 , N − N 0 }) + T (max{N 0 , N − N 0 }) + O(N ω log N0 ),
where N 0 is defined as in Algorithm 7, that is, N 0 is such i that stronglyConnected(i, i − 1) == false
or stronglyConnected(i, i + 1) == false and that minimizes |i − bN/2c|. Without loss of generality,
assume that N 0 ≥ N/2.
Denote by N 00 < N/2 the start of the strongly connected component that ends at position N 0 .
Observe that this component size satisfies N 0 − N 00 ≥ 2(N 0 − N/2). We consider two cases, which
intuitively distinguish whether the strongly connected component in the middle of the order is small
or large:
1. If N 0 ≥ 2/3N , then since N/2 − N 00 ≥ N 0 − N/2 (from the fact that N 0 is closest to N/2), we
get N 00 ≤ N − N 0 = (N − 3/2N 0 ) + N 0 /2 ≤ N 0 /2. This means that N 00 is a splitting point in
a recursive call on range [0, N 0 ], and we get bound
T (N ) = T (N 00 )+O((N 0 −N 00 )ω )+T (N −N 0 )+O(N ω log N0 ) ≤ T (1/3N )+T (1/3N )+O(N ω log N0 ),
where we have used that our claimed runtime bound T () is nondecreasing, so we can use
bounds N 00 ≤ 1/3N and N − N 0 ≤ 1/3N .
2. If N 0 ≤ 2/3N , then by the fact that N − N 0 ≤ 1/2N
T (N ) = T (N 0 ) + T (N − N 0 ) + O(N ω log N0 ) ≤ T (N/2) + T (2/3N ) + O(N ω log N0 ).
It is easy to see that T (N ) = C · N ω log N0 satisfies both of the recursive bounds (since ω ≥ 2),
given large enough constant C.
Thus plugging N0 = N for the total running time yields the claimed bound.

6

Matching lower bounds

A simple construction shows that any 2-reachability oracle for strongly connected graphs can also be
b = (Vb , E)
b from
used as a reachability oracle for any graph. Let G be a DAG. We create a graph G
G as follows: we add two new vertices s and t together with the edge (s, t), and for each vertex
b is strongly connected since we added paths
v ∈ V (G) we add the edges (v, s) and (t, v). Clearly, G
from each vertex u to any other vertex v, namely the path hu, s, t, vi. All the new paths between
b
vertices in V (G) contain the edge (s, t). Therefore, a vertex u has two edge-disjoint paths to v in G,
where u, v ∈ V (G), if and only if u has a path to v in G.
Additionally, for general graphs, there cannot be a significantly faster all-pairs 2-reachability
algorithm (than by a logarithmic factor), as our construction can produce all dominator trees, which
by definition encode the necessary information to answer reachability queries in constant time. As
computing reachability is asymptotically equivalent to matrix multiplication [8], there is no hope to
solve all-pairs 2-reachability in o(nω ).

22

7

Extension to vertex-disjoint paths

Our approach can be modified so that it reports the existence of two vertex-disjoint (rather than
edge-disjoint) paths for any pair of vertices. Although we can formulate the algorithms of Sections
3 and 4 so that they use separating vertices (rather than separating edges), here we sketch how
to obtain the same result via a standard reduction, which uses vertex-splitting. The details of the
reduction are as follows. From the original digraph G = (V, E), we compute a modified digraph
b = (Vb , E)
b by replacing each vertex v ∈ V by two vertices v + , v − ∈ Vb , together with the edge
G
b and replacing each edge (u, v) ∈ E by (u+ , v − ) ∈ E.
b (Thus, v + has the edges leaving
(v − , v + ) ∈ E,
−
v, and v has the edges entering v.) Then, for any pair of vertices u, v ∈ V , G contains two
b contains two edge-disjoint paths from u+ to v − .
vertex-disjoint paths from u to v if and only if G
b Let u, v be any vertices in G. If v is reachable from u in
Suppose that we apply our algorithm to G.
G but all paths from u to v in G contain a common vertex, then the algorithm reports a separating
b for the vertices u+ and v − . If e = (x− , x+ ), then x is a separating vertex for all paths
edge e ∈ E
from u to v in G. Otherwise, if e = (x+ , y − ), then (x, y) is a separating edge for all paths from u to
v in G and so both x and y are separating vertices.

8

An application: computing all dominator trees

Let s be an arbitrary vertex of G. Recall the bridge decomposition D of D (Section 4.2), which is
the forest obtained from D after deleting the bridges of flow graph G with start vertex s. As noted
earlier, Tv is the tree in D that contains vertex v, and rv denotes the root of Tv .
e of G with start vertex s, as the tree that results from D
We define the edge-dominator tree D
after contracting all vertices in each tree Tv into its root rv . For any vertex v and edge e = (x, y), e
e We
is contained in all paths in G from s to v if and only if (rx , ry ) is in the path from s to rv in D.
e the parent of a vertex in D.
e are roots in D.)
e (Both y and d(y)
denote by d(y)
Theorem 8.1. All sources vertex- and edge-dominator trees can be computed from GR 2e in O(n2 )
total time.
e with start vertex s, we look at the entries G 2e [s, v],
Proof. To construct the edge-dominator tree D
R
for all vertices v. We have the following cases: (a) If GR 2e [s, v] = ⊥ then v is not reachable from s
and we set rv = undefined. (b) If GR 2e [s, v] = > then we set rv = s. (c) If GR 2e [s, v] = (x, y) then
(x, y) is the last common edge in all paths from s to v. We mark y, set rv = y, and temporarily
e = x (note that rx may be unknown at this point). After we have processed the entries
assign d(y)
2e
GR [s, v] for all v, we make another pass over the marked vertices. Let y be a marked vertex, for
e = x. Then we set d(y)
e = rx . This completes the construction of
which we temporarily assigned d(y)
e which clearly takes O(n) time. By repeating this procedure for each vertex in V as a start vertex,
D,
we can compute all the edge-dominator trees, each rooted at a different vertex, in total O(n2 ) time.
The construction of D is very similar, we apply the standard trick of splitting each vertex into an inand out-vertex.
Theorem 8.1 enables us to obtain the following results.
Reachability queries after the deletion of an edge or vertex. We preprocess each edgee in O(n) so as to answer ancestor-descendant relations in constant time [21]. We
dominator tree D
23

also compute in O(n) time the number of descendants in D of every root r in D. This allows us to
answer various queries very efficiently:
• Given a pair of vertices s and t and an edge e = (x, y), we can test if G \ e contains a path
from s to t in constant time. This is because e is contained in all paths from s to t in G if and
only if the following conditions hold: e is a bridge of flow graph G with start vertex s (i.e.,
e = rx ) and y is an ancestor of rt in D.
e
ry = y and d(y)
• Similarly, given a vertex s and an edge e = (x, y), we can report in constant time how many
vertices become unreachable from s if we delete e from G. If e is a bridge of flow graph G with
start vertex s, then this number is equal to the number of descendants of y in D.
By computing all vertex-dominator trees of G, we can answer analogous queries for vertexseparators.
Computing junctions. A vertex s is a junction of vertices u and v in G, if G contains a path
from s to u and a path from s to v that are vertex-disjoint (i.e., s is the only vertex in common
in these paths). Yuster [26] gave a O(nω ) algorithm to compute a single junction for every pair of
vertices in a DAG. By having all dominator trees of a digraph G, we can also answer the following
queries.
• Given vertices s, u and v, test if s is a junction of u and v. This is true if and only if u and v
are descendants of distinct children of s in D. Hence, we can perform this test in constant
time.
• Similarly, we can report all junctions of a given a pair of vertices in O(n) time. Note that two
vertices may have n junctions (e.g., in a complete graph).
Computing critical nodes and critical edges. Let G be a directed graph. Define the reachability function f (G) as the number of vertex pairs hu, vi such that u reaches v in G, i.e., there is a
directed path from u to v. Here we consider how to compute the most critical node (resp., most
critical edge) of G, which is the vertex v (resp., edge e) that minimizes f (G \ v) (resp., f (G \ e)).
This problem was considered by Boldi et al. [3] who provided an empirical study of the effectiveness
of various heuristics. A related problem, where we wish to find the vertex
edge e) that

P |Cvi |(resp.,
minimizes the pairwise strong connectivity of G \ v (resp., G \ e), i.e., i 2 , where Ci are the
strongly connected components of G \ v (resp., G \ e), can be solved in linear time [11, 19].
The naive solution to find the most critical node of G is to calculate the transitive closure matrix
of G \ v, for all vertices v, and choose the vertex v that minimizes the number of nonzero elements.
This takes O(nω+1 ) time. Similarly, we can compute the most critical edge in O(mnω ) time. Here
we provide faster algorithms that exploit the computation of all dominator trees. We let Gu and Du
denote, respectively, the flow graph with start vertex u and its dominator tree. Also, we denote by
Du (v) the subtree of Du rooted at vertex v.
P
Computing the most critical node. Observe that f (G \ v) = u (|Du | − |Du (v)|), since for each vertex
u, the vertices that become unreachable from u after deleting v are exactly the descendants of v in
Du . Hence, we can process all dominator trees in O(n2 ) time and compute |Du (v)| for all vertices
u, v. Then, it is straightforward to compute f (G \ v), for a single vertex v, in O(n) time. Thus, we
obtain an algorithm that computes the most critical node of G in O(nω log n) total time.
24

Computing the most critical edge. Almost the same idea works for computing the most critical edge
of G. Here, we observe that v becomes unreachable from u in G \ e if and only if e = (x, y) is a
bridge of Gu and v ∈ Du (y). To exploit this observation, we store for each vertex y a list Ly of
pairs hu, xi such that (x, y) is a bridge in Gu . Note that hu, xi ∈ Ly implies that x is the parent
of y in Du .PThus, each list Ly has at most n − 1 pairs. Now, for each edge e = (x, y), we have
f (G \ e) = u:hu,xi∈Ly (|Du | − |Du (y)|). So, it is straightforward to compute f (G \ e), for a single
edge e, in O(n) time. To compute f (G \ e) for all edges e, observe that is suffices to process only the
pairs in all the Ly lists. Specifically, for each edge (x, y) we maintain a count unreach(x, y), initially
set to zero. When we process a pair hu, xi ∈ Ly , we increment unreach(x, y) by |Du | − |Du (y)|.
Clearly, after processing all pairs, the most critical edge is the one with maximum unreach value.
Since there are O(n2 ) pairs overall in all lists Ly , we obtain an algorithm that computes the most
critical edge of G in O(nω log n) total time.

9

Concluding remarks

In this paper we have shown that the all-pairs 2-reachability problem can be solved in O(nω log n)
time. Our algorithm produces a witness (separating edge or separating vertex) for every pair of
vertices for which 2-reachability does not hold. An important corollary of this result is that we
can compute all dominator trees of a digraph within the same time bound. Our work raises some
new, and perhaps intriguing, questions. First, since our algorithms can be used to answer queries
on whether there exists a path from vertex u to vertex v avoiding an edge e, can we extend our
approach to reporting avoiding paths within the same O(nω log n) (or any sub-cubic) running time?
Another interesting question is whether one can compute all-pairs k-reachability (or equivalently,
e ω ) time, or even in sub-cubic time, for k ≥ 3. It does not seem
the existence of (k − 1)-cuts) in O(n
easy to extend our techniques in this case.
Acknowledgments. We would like to thank Paolo Penna and Peter Widmayer for many useful
discussions on the problem.

References
[1] N. Alon, Z. Galil, O. Margalit, and M. Naor. Witnesses for boolean matrix multiplication and
for shortest paths. In 33rd Symposium on Foundations of Computer Science FOCS’92, pages
417–426. IEEE, 1992.
[2] S. Alstrup, D. Harel, P. W. Lauridsen, and M. Thorup. Dominators in linear time. SIAM
Journal on Computing, 28(6):2117–32, 1999.
[3] Paolo Boldi, Marco Rosa, and Sebastiano Vigna. Robustness of social and web graphs to node
removal. Social Network Analysis and Mining, 3(4):829–842, 2013.
[4] A. L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan, and J. R. Westbrook.
Linear-time algorithms for dominators and other path-evaluation problems. SIAM Journal on
Computing, 38(4):1533–1573, 2008.

25

[5] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal
of Symbolic Computation, 9(3):251–280, 1990.
[6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second
Edition. The MIT Press, 2001.
[7] A. Czumaj, M. Kowaluk, and A. Lingas. Faster algorithms for finding lowest common ancestors
in directed acyclic graphs. Theoretical Computer Science, 380(1-2):37–46, July 2007.
[8] M. J. Fischer and A. R. Meyer. Boolean matrix multiplication and transitive closure. In 12th
Annual Symposium on Switching and Automata Theory, pages 129–131. IEEE, 1971.
[9] W. Fraczak, L. Georgiadis, A. Miller, and R. E. Tarjan. Finding dominators via disjoint set
union. Journal of Discrete Algorithms, 23:2–20, 2013.
[10] L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-edge connectivity in directed
graphs. ACM Transactions on Algorithms, 13(1):9:1–9:24, 2016.
[11] L. Georgiadis, G. F. Italiano, and N. Parotsidis. Strong connectivity in directed graphs under
failures. In 28th ACM-SIAM Symposium on Discrete Algorithms SODA’17, pages 1880–1899,
2017.
[12] F. Grandoni and V. V. Williams. Improved distance sensitivity oracles via fast single-source
replacement paths. In 53rd IEEE Symposium on Foundations of Computer Science FOCS’12,
pages 748–757, Oct 2012.
[13] G. F. Italiano, L. Laura, and F. Santaroni. Finding strong bridges and strong articulation
points in linear time. Theoretical Computer Science, 447:74–84, 2012.
[14] R. Jin, Y. Xiang, N. Ruan, and H. Wang. Efficiently answering reachability queries on very
large directed graphs. In ACM SIGMOD International Conference on Management of Data
SIGMO’08, pages 595–608, New York, NY, USA, 2008. ACM.
[15] V. King and G. Sagert. A fully dynamic algorithm for maintaining the transitive closure.
Journal of Computer and System Sciences, 65(1):150 – 167, 2002.
[16] F. Le Gall. Powers of tensors and fast matrix multiplication. In 39th International Symposium
on Symbolic and Algebraic Computation ISSAC’14, pages 296–303, New York, NY, USA, 2014.
ACM.
[17] 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.
[18] K. Menger. Zur allgemeinen Kurventheorie. Fundamenta Mathematicae, 10:96–115, 1927.
[19] N. Paudel, L. Georgiadis, and G. F. Italiano. Computing critical nodes in directed graphs. In
19th Workshop on Algorithm Engineering and Experiments ALENEX’17, pages 43–57, 2017.
[20] P. Sankowski. Maximum weight bipartite matching in matrix multiplication time. Theoretical
Computer Science, 410(44):4480–4488, October 2009.

26

[21] R. E. Tarjan. Finding dominators in directed graphs. SIAM Journal on Computing, 3(1):62–89,
1974.
[22] R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM,
22(2):215–225, 1975.
[23] V. Vassilevska Williams. Faster replacement paths. In 22nd ACM-SIAM Symposium on Discrete
Algorithms SODA’11, pages 1337–1346, Philadelphia, PA, USA, 2011. Society for Industrial
and Applied Mathematics.
[24] V. Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In 44th
ACM Symposium on Theory of Computing STOC’12, pages 887–898, New York, NY, USA,
2012. ACM.
[25] O. Weimann and R. Yuster. Replacement paths and distance sensitivity oracles via fast matrix
multiplication. ACM Transactions on Algorithms, 9(2):14:1–14:13, March 2013.
e ω ) time. Theoretical Computer
[26] R. Yuster. All-pairs disjoint paths from a common ancestor in O(n
Science, 396(1):145–150, 2008.
[27] U. Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication.
Journal of the ACM, 49(3):289–317, May 2002.

27

