Near Optimal Parallel Algorithms for Dynamic DFS in
Undirected Graphs ∗

arXiv:1705.03637v1 [cs.DS] 10 May 2017

Shahbaz Khan

†‡

Abstract
Depth first search (DFS) tree is a fundamental data structure for solving various graph
problems. The classical algorithm [47] for building a DFS tree requires O(m + n) time for a
given undirected graph G having n vertices and m edges. Recently, Baswana et al. [6] presented
a simple algorithm for updating the DFS tree of an undirected graph after an edge/vertex
update in Õ(n) 1 time. However, their algorithm is strictly sequential. We present an algorithm
achieving similar bounds that can be easily adopted to the parallel environment.
In the parallel environment, a DFS tree can be computed from scratch using O(m) processors
in expected
Õ(1) time [2] on an EREW PRAM, whereas the best deterministic algorithm takes
√
Õ( n) time [2, 22] on a CRCW PRAM. Our algorithm can be used to develop optimal time
(upto poly log n factors) deterministic parallel algorithms for maintaining fully dynamic DFS
and fault tolerant DFS of an undirected graph.
1. Parallel Fully Dynamic DFS:
Given an arbitrary online sequence of vertex or edge updates, we can maintain a DFS tree
of an undirected graph in Õ(1) time per update using m processors on an EREW PRAM.
2. Parallel Fault tolerant DFS:
An undirected graph can be preprocessed to build a data structure of size O(m), such that
for any set of k updates (where k is constant) in the graph, a DFS tree of the updated
graph can be computed in Õ(1) time using n processors on an EREW PRAM. For constant
k, this is also work optimal (upto poly log n factors).
Moreover, our fully dynamic DFS algorithm provides, in a seamless manner, nearly optimal
(upto poly log n factors) algorithms for maintaining a DFS tree in the semi-streaming environment and a restricted distributed model. These are the first parallel, semi-streaming and
distributed algorithms for maintaining a DFS tree in the dynamic setting.

1

Introduction

Depth First Search (DFS) is a well known graph traversal technique. Right from the seminal work
of Tarjan [47], DFS traversal has played a central role in the design of efficient algorithms for many
fundamental graph problems, namely, strongly connected components, topological sorting [49],
dominators in directed graph [48], edge and vertex connectivity [16] etc.
Let G = (V, E) be an undirected connected graph having n vertices and m edges. The DFS
traversal of G starting from any vertex r ∈ V produces a spanning tree rooted at r called a DFS
tree, in O(m + n) time. For any rooted spanning tree of G, a non-tree edge of the graph is called a
back edge if one of its endpoints is an ancestor of the other in the tree. Otherwise, it is called a cross
∗

The preliminary version of this paper have been accepted to appear at SPAA 2017
Dept. of CSE, IIT Kanpur, India, email: shahbazk@cse.iitk.ac.in
‡
This research work was supported by Google India under the Google India PhD Fellowship Award.
1
Õ() hides the poly-logarithmic factors.
†

1

edge. A necessary and sufficient condition for any rooted spanning tree to be a DFS tree is that
every non-tree edge is a back edge. Thus, many DFS trees are possible for any given graph from a
given root r. However, if the traversal is performed strictly according to the order of edges in the
adjacency lists of the graph, the resulting DFS tree will be unique. Ordered DFS tree problem is
to compute the order in which the vertices are visited by this unique DFS traversal.
An algorithmic graph problem is modeled in a dynamic environment as follows. There is an
online sequence of updates on the graph, and the objective is to update the solution of the problem
efficiently after each update. In particular, the time taken to update the solution has to be much
smaller than that of the best static algorithm for the problem. A dynamic graph algorithm is
said to be fully dynamic if it handles both insertion and deletion updates, otherwise it is called
partially dynamic. Another, and more restricted, variant of a dynamic environment is the fault
tolerant environment. Here the aim is to build a compact data structure, for a given problem, that
is resilient to failures of vertices/edges and can efficiently report the solution after a given set of
failures.
Recently, Baswana et al. [6, 7] presented a fully dynamic algorithm for maintaining a DFS
√
tree of an undirected graph in Õ( mn) time per update. They also presented an algorithm for
updating the DFS tree after a single update in Õ(n) time. Prior to this work, only partially dynamic
algorithms were known for maintaining a DFS tree [8, 9, 19].
Now, major applications of dynamic graphs in the real world involve a huge amount of data,
which makes recomputing the solution after every update infeasible. Due to this large size of
data, it also becomes impractical for solving such problems on a single sequential machine because
of both memory and computation costs involved. Thus, it becomes more significant to explore
these dynamic graph problems on a computation model that efficiently handles large storage and
computations involved. In the past three decades a lot of work has been done to address dynamic
graph problems in parallel [10, 18, 37, 42, 44], semi-streaming [3, 4, 23, 26, 35], and distributed
(also called dynamic networks) [5, 28, 30, 33, 46] environments.
In this paper, we address the problem of maintaining dynamic DFS tree efficiently in the parallel
environment and demonstrate its applications in semi-streaming and distributed environments.

1.1

Existing results

In spite of the simplicity of a DFS tree, designing efficient parallel, distributed or streaming algorithms for a DFS tree has turned out to be quite challenging. Reif [39] showed that the ordered
DFS tree problem is a P -Complete problem. For many years, this result seemed to imply that the
general DFS tree problem, that is, the computation of any DFS tree of the graph is also inherently
sequential. However, Aggarwal et al. [1, 2] proved that the general DFS tree problem is in RNC
2 by designing a randomized EREW PRAM 3 algorithm that takes Õ(1) time. But the fastest
√
deterministic algorithm for computing general DFS tree in parallel still takes Õ( n) time [2, 22] in
CRCW PRAM 4 , even for undirected graphs. Moreover, the general DFS tree problem has been
shown to be in NC for some special graphs including DAGs [21, 52] and planar graphs [24, 29, 45]
(see [20] for a survey). In fact for random graphs in G(n, p) model 5 [15], Dyer and Frieze [14]
proved that even ordered DFS tree problem is in RNC. Whether general DFS tree problem is in
NC is still a long standing open problem.
2

NC is the class of problems solvable using O(nc1 ) processors in parallel in O(logc2 n) time, for any constants c1
and c2 . The class RNC extends NC to allow access to randomness.
3
Exclusive Read Exclusive Write (EREW) restricts any two processors to simultaneously read or write the same
memory cell. Concurrent Read Concurrent Write (CRCW) does not have this restriction.
4
It essentially shows DFS to be NC equivalent of minimum-weight perfect matching, which is in RNC whereas
√
its best deterministic algorithm requires Õ( n) time.
5
G(n, p) denotes a random graph where every edge of the graph exists independently with probability p.

2

In the semi-streaming environment, the input graph is accessed in the form of a stream of
graph edges, where the algorithm is allowed only O(n) local space. The DFS tree can be trivially
computed using O(n) passes over the input graph in the semi-streaming environment, each pass
adding one vertex to the DFS tree. However, computing the DFS tree in Õ(1) passes is considered
hard [17]. To the best of our knowledge, it remains an open problem to compute the DFS tree
using even o(n) passes in any relaxed streaming environment [36, 40].
Computing a DFS tree in a distributed setting was widely studied in 1980’s and 1990’s. A
DFS tree of the given graph can be computed in O(n) rounds, with various trade offs of number of
messages passed and size of each message. If the size of a message is allowed to be O(n), the DFS
tree can be built using O(n) messages [31, 34, 43]. However, if the size of a message is limited to
Õ(1), the number of messages required is O(m) [11, 32, 51].
√
Thus, to maintain a DFS tree in dynamic setting, each update requires Õ( n) time on a CRCW
PRAM in deterministic parallel setting, O(n) passes in the semi-streaming setting and O(n) rounds
in the distributed setting, which is very inefficient. Hence, exploring the dynamic maintenance of
a DFS tree in parallel, semi-streaming and distributed environments seems to be a long neglected
problem of practical significance.
We present optimal algorithms (up to poly log n factors) for maintaining a fully dynamic DFS
tree for an undirected graph under both edge and vertex updates on these models.

1.2

Our Results

We consider an extended notion of updates wherein an update could be either insertion/deletion of
a vertex or insertion/deletion of an edge. Furthermore, an inserted vertex can be added with any
set of incident edges to the graph.
In the parallel setting, our main result can be succinctly described as follows.
Theorem 1. Given an undirected graph and its DFS tree, it can be preprocessed to build a data
structure of size O(m) in O(log n) time using m processors on an EREW PRAM such that for any
update in the graph, a DFS tree of the updated graph can be computed in O(log3 n) time using n
processors on an EREW PRAM.
With this result at the core, we easily obtain the following results.
1. Parallel Fully Dynamic DFS:
Given any arbitrary online sequence of vertex or edge updates, we can maintain a DFS tree of
an undirected graph in O(log3 n) time per update using m processors on an EREW PRAM.
2. Parallel Fault tolerant DFS:
An undirected graph can be preprocessed to build a data structure of size O(m) such that for
any set of k(≤ log n) updates in the graph, a DFS tree of the updated graph can be computed
in O(k log2k+1 n) time using n processors on an EREW PRAM.
Our fully dynamic algorithm and fault tolerant algorithm (for constant k), clearly take optimal
time (up to poly log n factors) for maintaining a DFS tree. Our fault tolerant algorithm (for constant
k) is also work optimal (upto poly log n factors) since a single update can lead to Θ(n) changes in
the DFS tree. Moreover, our result also establishes that maintaining a fully dynamic DFS tree for
an undirected graph is in NC (which is still an open problem for DFS tree in the static setting).

1.3

Applications of Parallel Fully Dynamic DFS

Our parallel fully dynamic DFS algorithm can be seamlessly adapted to the semi-streaming and
distributed environments as follows.
3

1. Semi-streaming Fully Dynamic DFS:
Given any arbitrary online sequence of vertex or edge updates, we can maintain a DFS tree
of an undirected graph using O(log2 n) passes over the input graph per update by a semistreaming algorithm using O(n) space.
2. Distributed Fully Dynamic DFS:
Given any arbitrary online sequence of vertex or edge updates, we can maintain a DFS tree of
an undirected graph in O(D log2 n) rounds per update in the synchronous CON GEST (n/D)
model 6 using O(nD log2 n + m) messages of size O(n/D) requiring O(n) space on each
processor, where D is diameter of the graph.
Our semi-streaming algorithm clearly takes optimal number of passes (up to poly log n factors)
for maintaining a DFS tree. Our distributed algorithm that works in a restricted CON GEST (B)
model, also arguably requires optimal rounds (up to poly log n factors) because it requires Ω(D)
rounds to propagate the information of the update throughout the graph. Since almost the whole
DFS tree may need to be updated due to a single update in the graph, every algorithm for maintaining a DFS tree in the distributed setting will require Ω(D) rounds 7 . This essentially improves
the state of the art for the classes of graphs with o(n) diameter.

1.4

Overview

We now describe a brief overview of our result. Baswana et al. [6] proved that updating a DFS tree
after any update in the graph is equivalent to rerooting disjoint subtrees of the DFS tree. They
also presented an algorithm to reroot a DFS tree T (or its subtree), originally rooted at r to a
new root r0 , in Õ(n) time. It starts the traversal from r0 traversing the path connecting r0 to r in
T . Now, the subtrees hanging from this path are essentially the components of the unvisited graph
(the subgraph induced by the unvisited vertices of the graph) due to the absence of cross edges. In
the updated DFS tree, every such subtree, say τ , shall hang from an edge emanating from τ to the
path from r0 to r. Let this edge be (x, y), where x ∈ τ . Thus, we need to recursively reroot τ to
the new root x and hang it from (x, y) in the updated DFS tree. Note that this rerooting can be
independently performed for different subtrees hanging from tree path from r0 to r.
At the core of their result, they use a property of the DFS tree, that they called components
property, to find the edge (x, y) efficiently, using a data structure D0 . However, as evident from
the discussion above, their rerooting procedure can be strictly sequential in the worst case. This is
because the size of a subtree τ to be rerooted can be almost equal to that of the original tree T .
As a result, O(n) sequential reroots may be required in the worst case. Our main contribution is
an algorithm that performs this rerooting efficiently in parallel.
Our algorithm ensures that rerooting is completed in Õ(1) steps as follows. At any point of
time, we ensure that every component c of the unvisited graph is either of type C1, having a single
subtree of T , or of type C2, having a path pc and a set of subtrees of T having edges to pc . Note that
in [6] every component of the unvisited graph is of type C1. We define three types of traversals,
namely, path halving (also used by [6]), disintegrating traversal and disconnecting traversal. We
prove that using a combination of O(1) such traversals, for every component c of the unvisited
graph, either the length of pc is halved or the size of largest subtree in c is halved. Moreover, these
traversals can be performed in O(log n) time on |c| processors using the components property and
6

CON GEST (B) model is the standard CON GEST model [38] where message size is relaxed to B words.
For an algorithm maintaining the whole DFS tree at each node, even our message size is optimal. This is because
an update of size O(n) (vertex insertion with arbitrary set of edges) will have to be propagated throughout the network
in the worst case. In O(D) rounds, it can only be propagated using messages of size Ω(n/D). (see Section 6.2 for
details).
7

4

a data structure D (answering similar queries as D0 ). However, since our algorithm ensures that
each vertex is queried by D only Õ(1) times (unlike [6]), our data structure D is much simpler than
D0 .
Furthermore, both our algorithm and the algorithm by [6] use the non-tree edges of the graph
only to answer queries on data structure D (or D0 ). The remaining operations (except for queries
on D) required by our algorithm can be performed using only edges of T in O(n) space. As a
result, our algorithm being efficient in parallel setting (unlike [6]), can also be adapted to the
semi-streaming and distributed model as follows. In the semi-streaming model, the passes over the
input graph are used only to answer the queries on D, where the parallel queries on D made by
our algorithm can be answered simultaneously using a single pass. Our distributed algorithm only
needs to store the current DFS tree at each node and the adjacency list of the corresponding vertex
abiding the restriction of O(n) space at each node. Again, the distributed computation is only used
to answer queries on D.

2

Preliminaries

Let G = (V, E) be any given undirected graph on n = |V | vertices and m = |E| edges. The
following notations will be used throughout the paper.
• par(w) : Parent of w in T .
• T (x) : The subtree of T rooted at vertex x.
• path(x, y) : Path from vertex x to vertex y in T .
• LCA(x, y) : Lowest common ancestor of x and y in T .

• root(T 0 ) : Root of a subtree T 0 of T , i.e., root T (x) = x.
• T ∗ : The DFS tree computed by our algorithm for the updated graph.
A subtree T 0 is said to be hanging from a path p if the root(T 0 ) is a child of some vertex
on the path p and does not belong to the path p. Unless stated otherwise, a component refers
to a connected component of the unvisited graph. We refer to a path p in a DFS tree T as an
ancestor-descendant path if one of its endpoints is an ancestor of the other in T .
For our distributed algorithm, we use the synchronous CON GEST (B) model [38]. For the
dynamic setting, Henzinger et al. [25] presented a model that has a preprocessing stage followed
by an alternating sequence of non-overlapping stages for update and recovery (see Section 6.2 for
details). We use this model with an additional constraint of space restriction of O(n) size at
each node. In the absence of this restriction, the whole graph can be stored at each node, where
an algorithm can trivially propagate the update to each node and the updated solution can be
computed locally. Also, we allow the deletion updates to be abrupt, i.e., the deleted link/node
becomes unavailable for use instantly after the update.
In order to handle disconnected graphs, we add a dummy vertex r to the graph and connect it
to all the vertices. Our algorithm maintains a DFS tree rooted at r in this augmented graph, where
each child subtree of r is a DFS tree of a connected component in the DFS forest of the original
graph.
We shall now define some queries that are performed by our algorithm on the data structure
D (similar queries on D0 also used in [6]). Let v, w, x, y ∈ V , where path(x, y) and path(v, w) (if
required) are ancestor-descendant paths in T . Also, no vertex in path(v, w) is a descendant of any
vertex in path(x, y). We define the following queries.
5


1. Query w, path(x, y) : among all the edges from w that are incident on path(x, y) in G, return
an edge that is incident nearest to x on path(x, y).

2. Query T (w), path(x, y) : among all the edges from T (w) that are incident on path(x, y) in
G, return an edge that is incident nearest to x on path(x, y).

3. Query path(v, w), path(x, y) : among all the edges from path(v, w) that are incident on
path(x, y) in G, return an edge that is incident nearest to x on path(x, y).
Let the descendant vertices of the three queries described above be w, T (w) and path(v, w)
respectively. A set of queries on the data structure D are called independent if the descendant
vertices of these queries are disjoint.
Baswana et al. [6] described the components property of a DFS tree as follows.
r
C1

e01
e1

w

C2
e02

v

e2

Figure 1: Edges e01 and e02 can be ignored during the DFS traversal (reproduced from [7]).
Lemma 1 (Components Property [6]). Let T ∗ be the partially built DFS tree and v be the vertex
currently being visited. Let C1 , .., Ck be the connected components of the subgraph induced by the
unvisited vertices. For any two edges ei and e0i from Ci that are incident respectively on v and some
ancestor (not necessarily proper) w of v in T ∗ , it is sufficient to consider only ei during the DFS
traversal, i.e., the edge e0i can be safely ignored.
Ignoring e0i during the DFS traversal, as stated in the components property, is justified because
will appear as a back edge in the resulting DFS tree (refer to Figure 1). The edge ei can be found
by querying the data structure D (or D0 in [6]). The DFS tree is then updated after any update
in the graph by reducing it to rerooting disjoint subtrees of the DFS tree using the components
property. Rerooting a subtree T (v) at a new root r0 ∈ T (v) involves restructuring the tree T (v) to
be now rooted at r0 such that the new tree is also a DFS tree of the subgraph induced by T (v). This
reduction will henceforth be referred as the reduction algorithm and is described in the following
section.
e0i

3

Reduction Algorithm

We now describe how updating a DFS tree after any kind of update in the graph is equivalent to a
simple procedure, i.e., rerooting disjoint subtrees of the DFS tree. Note that similar reduction was
also used by Baswana et al. [6] but we describe it here for the sake of completeness as follows (see
Figure 2).
1. Deletion of an edge (u, v):
If (u, v) is a back edge in T , simply delete it from the graph. Otherwise, let u = par(v) in
6

r

r

r

r
v1

u01

u0

v2

u02

u

w
v

u
v1

v0
v0

u

v

u
v2

v10

v30

v20

v3

v40

vj

(i)

(ii)

(iii)

v4

(iv)

Figure 2: Updating the DFS tree after a single update: (i) deletion of an edge, (ii) insertion
of an edge, (iii) deletion of a vertex, and (iv) insertion of a vertex. The algorithm reroots the
marked subtrees (marked in violet) and hangs it from the inserted edge (in case of insertion) or the
lowest edge (in case of deletion) on the marked path (marked in blue) from the marked subtree.
(reproduced from [6])
T . The algorithm finds the lowest edge (u0 , v 0 ) on the path(u, r) from T (v), where v 0 ∈ T (v).
The subtree T (v) can then be rerooted to the new root v 0 and hanged from u0 using (u0 , v 0 )
to get the final tree T ∗ .
2. Insertion of an edge (u, v):
In case (u, v) is a back edge, simply insert it in the graph. Otherwise, let w be the LCA of
u and v in T and v 0 be the child of w such that v ∈ T (v 0 ). The subtree T (v 0 ) can then be
rerooted to the new root v and hanged from u using (u, v) to get the final tree T ∗ .
3. Deletion of a vertex u:
Let v1 , ..., vc be the children of u in T . For each subtree T (vi ), the algorithm finds the lowest
edge (u0i , vi0 ) on the path(par(u), r) from T (vi ), where vi0 ∈ T (vi ). Each subtree T (vi ) can then
be rerooted to the new root vi0 and hanged from u0i using (u0i , vi0 ) to get the final tree T ∗ .
4. Insertion of a vertex u:
Let v1 , ..., vc be the neighbors of u in the graph. Arbitrarily choose a neighbor vj and make u
the child of vj in T ∗ . For each vi , such that vi ∈
/ path(vj , r), let T (vi0 ) be the subtree hanging
0
from path(vj , r) such that vi ∈ T (vi ). Each subtree T (vi0 ) can then be rerooted to the new
root vi and hanged from u using (u, vi ) to get the final tree T ∗ .
In case of a vertex update, multiple subtrees may be required to be rerooted by the algorithm.
Let these subtrees be T1 , ..., Tc . Notice that each of these subtrees can be rerooted independent of
each other, and hence in parallel. However, in order to perform the reduction algorithm efficiently
in parallel, we require a structure to answer the following queries efficiently in parallel. (a) Finding
LCA of two vertices in T . (b) Finding the highest edge from a subtree T (v) to a path in T (a
query on data structure D). In addition to these we also require several other types of queries to
be efficiently answered in parallel setting as testing if an edge is back edge, finding vertices on a
path, child subtree of a vertex containing a given vertex etc. However, these can easily be answered
using LCA queries as described in Section 5.1. Thus, we have the following theorem.

7

Theorem 2. Given an undirected graph G and its DFS tree T , any graph update can be reduced
to independently rerooting disjoint subtrees of T by performing O(1) sets of independent queries on
the data structure D and O(1) sets of LCA queries on T , where each set has at most n queries.
Remark. The implementation of reduction algorithm is simpler in distributed and semi-streaming
environments, where any operation on the DFS tree T can be performed locally without any distributed computation or passes over the input graph respectively. Hence, for these environments the
reduction algorithm requires only O(1) sets of independent queries on the data structure D.

4

Rerooting a DFS tree

We now describe the algorithm to reroot a subtree T (r0 ) of the DFS tree T , from its original root r0
to the new root r∗ . Also, let the data structure D be built on T (see Section 2). Also, we maintain
the following invariant: at any moment of the algorithm, every component c of the unvisited graph
can be of the following two types:
C1: Consists of a single subtree τc of the DFS tree T .
C2: Consists of a single ancestor-descendant path pc and a set Tc of subtrees of the DFS tree T
having at least one edge to pc . Note that for any τ1 , τ2 ∈ Tc , there is no edge between τ1 and
τ2 since T is a DFS tree.
Moreover, for every component c we also have a vertex rc ∈ c from which the DFS tree of the
component c would be rooted in the final DFS tree T ∗ .
The algorithm is divided into log n phases, where each phase is further divided into log n stages.
At the end of phase Pi , every subtree of any component c (τc or subtrees in Tc ) has at most n/2i
vertices. During phase Pi , every component has at least one heavy subtree (having > n/2i vertices).
If no such tree exists, we move the component to the next phase. We denote the set of these heavy
subtrees by Tc . For notational convenience, we refer to the heaviest subtree of every component
c as τc , even for components of type C2. Hence, for any component of type C1 or C2, we have
τc ∈ Tc . Clearly the algorithm ends after log n phases as every component of the unvisited graph
would be empty.
At the end of stage Sj of a phase, the length of pc in each component c is at most n/2j . If
|pc | ≤ n/2j , we move the component c to the next stage. Further, for any component c of type
C1, the value of |pc | is zero, so we move such components to the last stage of the phase, i.e., Slog n .
Clearly at the end of log n stages, each component would be of type C1.
In the beginning of the algorithm, we have the component induced by T (r0 ) of type C1 where
rc = r∗ . Note that during each stage, different connected components of the unvisited graph can
be processed independent of each other in parallel.

Algorithm
We now describe how a component c in phase Pi and stage Sj is traversed by our algorithm. The
aim is to build a partial DFS tree for the component c rooted at rc , that can be attached to the
partially built DFS tree T ∗ of the updated graph. Note that this has to be performed in such a
manner that every component of the unvisited part of c is of type C1 or C2 only.
Now, in order to move to the next phase, we need to ensure that for every component c0 of the
unvisited part of c, |τc0 | ≤ n/2i . As described above, after log n stages every component c0 is of
type C1. Thus, we perform a disintegrating traversal of τc which ensures that every component of
the unvisited part of c can be moved to the next phase.
8

r0

r0

pc

pc

x

vl

vl

y

rc
rc

rc

vH

(a)

(b)

x

(c)

Figure 3: The three easier types of traversals shown in blue dotted lines, (a) Disintegrating traversal,
(b) Path Halving and (c) Disconnecting traversal.
During Sj , in order to move to the next stage, we need to ensure that for every component c0
of the unvisited part of c, either |pc0 | ≤ n/2j (moving it to next stage) or |τc0 | ≤ n/2i (moving it
to next phase). The component is processed based on the location of rc in c as follows. If rc ∈ pc ,
we perform path halving which ensures the components move to the next stage. If rc ∈ τ ∈
/ Tc ,
we perform a disconnecting traversal of τ followed by path halving of pc such that the unvisited
components of τ are no longer connected to residual part of pc , moving them to the next phase.
The remaining components of c moves to the next stage due to path halving.
We shall refer to disintegrating traversal, path halving and disconnecting traversal as the simpler
traversals. The difficult case is when rc ∈ τ ∈ Tc . Here, some trivial cases can be directly
processed by the simpler traversals mentioned above. For the remaining cases we perform heavy
subtree traversal of τ which shall ensure that the unvisited part of c reduces to those requiring
simpler traversals. Refer to Procedure Reroot-DFS in Appendix A for the pseudo-code of the main
algorithm.
We now describe the different types of traversals in detail. For any component c, we refer to the
smallest subtree of τ ∈ Tc that has more than n/2i vertices as T (vH ). Since n/2i−1 ≥ |τ | > n/2i ,
vH is unique. Also, let r0 = root(τ ) (if rc ∈ τ ) and vl = LCA(rc , vH ).

4.1

Disintegrating Traversal

Consider a component c of type C1 with new root rc ∈ τc in phase Pi (n/2i < |τc | ≤ n/2i−1 ). We
first find the vertex vH . We then traverse along the tree path path(rc , vH ), adding it to T ∗ see
Figure 3 (a) . Now, the unvisited part of c consists of path(par(vl ), r0 ) (say p) and the subtrees
hanging from path(rc , r0 ) and path(vl , vH ). Notice that p is an ancestor-descendant path of T and
each subtree has at most n/2i vertices. Each subtree not having an edge to p corresponds to a
separate component of type C1. The path p and the remaining subtrees (having an edge to p)
form a component of type C2. For each component c∗ , we also need to find the new root rc∗ for
the updated DFS tree of the component. Using the components property, we know rc∗ has the
lowest edge from c∗ on the path p∗ , where p∗ is the newly attached path to T ∗ described above.
Both these queries (finding an edge to p and the lowest edge on p∗ ) can be answered by our data
structure D (see Section 2). Thus, every component c∗ can be identified and moved to next phase.
Refer to Procedure DisInt-DFS in Appendix A for the pseudo code.
Remark. If rc = r0 , this traversal can also be performed on a subtree from a component c of type
9

C2 achieving similar result. This is possible because no new path p would be formed and we still
get components of type C1 and C2 (being connected to a single path pc ).

4.2

Path Halving

Consider a component of type C2 with rc ∈ pc = path(x, y). We first find the farther end of pc ,
say x, where |path(rc , x)| ≥ |path(rc , y)|. We then traverse from rc to x adding path(rc , x) to the
tree T ∗ see Figure 3 (b) . The component c0 of type C2 thus formed will have pc0 of length at
most half of pc . Now, the subtrees in c having an edge to pc0 would be a part of c0 . The remaining
subtrees would form individual components of type C1. Again, the new root of each component
can be found using D by querying for the lowest edge on the path(rc , x) added to T ∗ . Refer to
Procedure Path-Halving-DFS in Appendix A for the pseudo code.

4.3

Disconnecting Traversal

Consider a component of type C2 with rc ∈ τ , where τ ∈
/ Tc . We traverse τ from rc to reach pc ,
which is then followed by path halving of pc . The goal is to ensure that the unvisited part of τ is
not connected to the unvisited part of pc (say p0 ) after path halving, moving it to the next phase.
The remaining subtrees of c with p0 will move to the next stage as a result of path halving of pc .
Now, if at least one edge from
τ is present on the upper half of pc , we find the highest edge

from τ to pc see Figure 3 (c) . Otherwise, we find the lowest edge from τ to pc . Let it be (x, y),
where y ∈ pc and x ∈ τ . This ensures that on entering pc through y, path halving would ensure
that all the edges from τ to pc are incident on the traversed part of pc (say p).
We perform the traversal from rc to x similar to the disintegrating traversal along path(rc , x),
attaching it to T ∗ . Since none of the components of unvisited part of τ are connected to p0 , all the
components formed would be of type C1 or C2 as described in Section 4.1. However, while finding
the new root of each resulting component c0 , we also need to consider the lowest edge from the
component on p. Further, since τ ∈
/ Tc , size of each subtree in the resulting components is at most
n/2i . Thus, the resultant components of τ are moved to the next phase (see Procedure DisCon-DFS
in Appendix A for pseudo code).
Remark. If rc ∈ T (vH ), this traversal can also be performed on a τ ∈ Tc getting a similar result.
This is because each subtree in resultant components of τ will have size at most n/2i moving it to
the next phase. However, if rc ∈
/ T (vH ) the resultant component c0 of type C2 formed can have a
heavy subtree and a path pc0 of arbitrary length. This is not permitted as it will move the component
to some earlier stage in the same phase.

4.4

Heavy Subtree Traversal

Consider a component c of type C2 with rc ∈ τ , where τ ∈ Tc . As described earlier, if rc = root(τ ) or
rc ∈ T (vH ), the heavy subtree τ can be processed using disintegrating or disconnecting traversals
respectively. Otherwise, we traverse it using one of three scenarios. Our algorithm checks each
scenario in turn for its applicability to τ , eventually choosing a scenario to perform an l, p or r
traversal (see Figure 4). This traversal ensures that it is followed by a simpler traversal described
earlier, so that each component will either move to the next phase or the next stage. We shall
also prove that these scenarios are indeed exhaustive, i.e., for any τ , one of the scenarios is indeed
applicable ensuring that each component moves to the next stage/phase. The following lemma
describes the conditions when a scenario is applicable.
Lemma 2 (Applicability Lemma). After a traversal of path p∗ in a subtree τ ∈ Tc , every component
of unvisited part of c can be moved to the next phase/stage using a simpler traversal if
10

pc
r

pc

0

r

pc

0

r

yp
y1

yd

y2

yr

x1

x2

vl

vl
vL

vl
vL

rc

rc
vH

(a)

0

vL
xp

vP
vH

rc

xd

vP
xr

(b)

vR
vH

(c)

Figure 4: The three scenarios for Heavy Subtree Traversal (blue dotted lines) showing (a) l traversal,
(b) p traversal and (c) r traversal.
A1 : Traversal of p∗ produces components of type C1 or C2 only,
A2 : The subtree T (vH ) is connected to pc (if in component of type C2),
A3 : The lowest edge on p∗ from the component containing pc is not a back edge from the subtree
containing T (vH ) with its end point outside T (vH ).
Proof. Consider any traversal satisfying the above criteria, which forms components of type C1
and C2 only. For each such component c0 , we find the lowest edge e0 from c0 to the traversed path,
giving the new root rc0 . Every component which does not contain pc or T (vH ) can be directly
moved to the next phase with root rc0 , because the remaining subtrees of τ (not containing T (vH ))
cannot be heavy. In case the component containing T (vH ) is of type C1 it can be moved to the
last stage of the phase. In case the component c0 containing pc does not contain T (vH ), we have
rc0 ∈ pc or rc0 ∈ τ 0 (a non-heavy subtree of τ ), moving c0 to the next stage after performing path
halving or disconnecting traversal of τ 0 respectively. Due to the second condition, this only leaves
the component c0 of type C2 having both pc and a subtree T (vh ) ∈ Tc0 which contains T (vH ).
The third condition prevents e0 from being a back edge with rc0 ∈ T (vh ) and rc0 ∈
/ T (vH ). The
0
remaining cases can be processed by path halving (if rc ∈ pc ), disconnecting traversal (rc0 ∈
/ T (vh )
or rc0 ∈ T (vH )) or disintegrating traversal (rc0 = vh , includes e0 being a tree edge) respectively.
Remark. Applicability lemma is employed when p∗ does not traverse through T (vH ), in which
case the unvisited component trivially moves to the next stage/phase. In such a case, the traversal
preceding p∗ was clearly applicable. Condition A2 ensures that the heavy subtree containing T (vH )
does not form a component c0 with arbitrary length of path pc0 , as this can move it to some previous
stage which is not allowed. Because of the same reason disconnecting traversal is not used on such
heavy subtrees.
We now briefly describe the three scenarios, namely, l, p and r traversals and define a few
notations related to them (shown in Figure 4). The l, p and r traversals follow the path shown in
figure (using blue dotted lines) which shall henceforth be referred as p∗L , p∗P and p∗R respectively.
Both p and r traversals use a back edge during the traversal, denoted by (xp , yp ) and (xr , yr )
respectively. Further, we refer to the subtrees containing vH that hangs from p∗L , p∗P and p∗R as
T (vL ), T (vP ) and T (vR ) respectively. We shall refer to the subtree hanging from the traversed
11

path (p∗L , p∗P or p∗R ) with an edge to pc as eligible subtrees. In each scenario we ensure A1 and
A2 by construction, implying that the scenario will not be applicable only if the third condition is
violated. Thus, we only need to find the lowest edge on traversed path from the eligible subtrees,
to determine the applicability of a scenario. Also, the edges (xp , yp ) and (xr , yr ) are chosen in such
a way that if l and p traversals are not applicable, then r traversal always satisfies applicability
lemma, with the lowest edge from component containing pc being (xd , yd ), where xd ∈ τd 6= T (vR ).
Scenario 1: l traversal
Consider the traversal shown in Figure 4 (a), where p∗L = path(rc , r0 ). Since, this traversal does
not create a new non-traversed path, the first two conditions of applicability lemma are satisfied.
We find the lowest edge on p∗L (highest edge on path(rc , r0 )) from pc and the eligible subtrees, say
(x1 , y1 ), where y1 ∈ p∗L . In case this edge satisfies the third condition of applicability lemma, we
perform the traversal otherwise move to the next scenario.
Remark. This scenario is not applicable only if (x1 , y1 ) is a back edge with x1 ∈ T (vL ) and
x1 ∈
/ T (vH ).
Scenario 2: p traversal
Consider the traversal shown in Figure 4 (b), where p∗P = path(rc , xp ) ∪ (xp , yp ) ∪ path(yp , par(vl )).
To perform this traversal, we choose (xp , yp ) along with (xd , yd ) such that either p traversal is
applicable, or r traversal is applicable using (xd , yd ). We now describe how such a choice of (xp , yp )
and (xd , yd ) can be made. Let τd and τp (if any), be the subtrees hanging from path(vL , vH )
containing xd and xp respectively.
Choice of (xp , yp ) and (xd , yd )

We find the highest edge on path(rc , r0 ) from the eligible subtrees hanging from p∗L except T (vL )
and the eligible subtrees hanging from path(vL , vH ). This edge is stored as (xd , yd ), where yd ∈
path(rc , r0 ), is the edge to be used in Scenario 3. The corresponding subtree to which xd belongs
is τd . Next, we find the edge (xp , yp ), with xp ∈ T (vL ) and yp ∈ path(yd , r0 ), which has the lowest
LCA(xp , vH ) on path(vL , vH ). However, if (xd , yd ) does not exist, (xp , yp ) is found by considering
whole of path(rc , r0 ) instead of path(yd , r0 ). The existence of back edge (x1 , y1 ) implies the following
properties of the computed edges (xp , yp ) and (xd , yd ).
Lemma 3. The edge (xp , yp ), which is a back edge, always exists and when used for p traversal
satisfies A1 and A2 .
Proof. Recall that (x1 , y1 ) is the highest edge on path(rc , r0 ) from the eligible subtrees hanging from
the p∗L , whereas (xd , yd ) is the highest edge on path(rc , r0 ) from a more restricted set of subtrees.
Thus, y1 is at least as high as yd on path(rc , r0 ). Now, since (x1 , y1 ) is a back edge with x1 ∈ T (vL )
(see remark in Scenario 1), (x1 , y1 ) is also a valid edge for (xp , yp ) ensuring its existence of p edge.
Further, (xp , yp ) is also a back edge because (x1 , y1 ) is a back edge and LCA(xp , vH ) is at most as
high as LCA(x1 , vH ) ensuring xp 6= vL .
Now, consider the p traversal using (xp , yp ), which produces an untraversed path, say p0 =
path(par(yp ), r0 ). To prove that this traversal produces only components of type C1 and C2 (the
condition A1 ), we only need to prove that any eligible subtree (subtree hanging from p∗P with an
edge to pc ) is not connected to p0 . This is because p0 itself is not connected directly to pc by an
edge (as x1 ∈
/ pc ). We first prove this property for the subtrees queried for finding (xd , yd ). Since
yp is at least as high as yd on path(rc , r0 ), any such subtree will not be connected to p0 . Now, we
12

are left to prove this property for the remaining subtrees of T (vL ) hanging from p∗P with an edge to
pc . The only such subtree is T (vP ), the subtree hanging from p∗P which contains T (vH ) (satisfying
A2 ). Since, among all the edges (x, y) from T (vL ) to path(yd , r0 ), xp is the vertex with lowest
LCA(x, vH ), the subtree T (vP ) is not connected to p0 . This is because for any such edge (x, y),
where x ∈ T (vP ), would have LCA(x, vH ) lower than vP , which is clearly lower than LCA(xp , vH )
on path(vL , vH ).
Lemma 4. On performing r traversal using any edge (xr , yr ), which satisfies (i) xr ∈ T (vP ) ∪ τp
(if any), and (ii) the conditions A1 and A2 , the r traversal is applicable with the lowest edge from
an eligible subtree to p∗R being (xd , yd ) (from the eligible subtree τd ), if either τd 6= τp or τd is not
traversed by p∗R .
Proof. Since (xp , yp ) is the edge to path(yd , r0 ) with the lowest LCA(xp , vH ), the subtree T (vP ) does
not have an edge to path(yd , r0 ). Thus, any subtree of T (vP ), even if eligible, cannot have an edge
on path(rc , r0 ) higher
than (xd , yd ). As a result, if r traversal is performed with xr ∈ T (vP ) ∪ τp ,

see Figure 4 (c) , the highest edge on path(rc , r0 ) (and hence lowest on p∗R ) can be found by
querying the same eligible subtrees as the ones queried while computing (xd , yd ). Also, if some part
of path(rc , r0 ) is not traversed by r traversal, it would effect this lowest edge only if it has an edge
to pc or some eligible subtree, which is avoided by second condition. Finally, it also requires the
subtree containing xd to remain connected to pc and leave xd untraversed. Since LCA(xp , vH ) is
atleast as low as LCA(xd , vH ), T (vP ) and τd are disjoint. Hence, the only way in which r traversal
traverses τd is if xp ∈ τp and τp = τd .
Thus, Lemma 3 ensures that our traversal can follow p∗P as shown in Figure 4 (b). To verify
the third condition of applicability lemma, we find the new root for the component having path pc
as follows. We find the lowest edge on p∗P from pc and the eligible subtrees hanging from p∗P , say
(x2 , y2 ), where y2 ∈ p∗P . In case this edge satisfies A3 , we perform the traversal otherwise move to
the next scenario.
Remark. This scenario is not applicable only if (x2 , y2 ) is a back edge with x2 ∈ T (vP ) and
x2 ∈
/ T (vH ).
Scenario 3: r traversal
Consider the traversal shown in Figure 4 (c), where p∗R = path(rc , xr ) ∪ (xr , yr ) ∪ path(yr , r0 ).
We choose (x2 , y2 ) as (xr , yr ). However, while computing (x2 , y2 ), τp (if exists) would have been
partially traversed. Hence, if the lowest edge from τp to path(rc , r0 ), say (x02 , y20 ), has y20 lower than
yr on path(rc , r0 ), τp would be connected to both pc and path(par(vl ), y2 )\{y2 }. This creates a
component having pc which is not of type C1 or C2 violating A1 . In such a case we choose (x02 , y20 )
as (xr , yr ). The existence of back edge (x2 , y2 ) implies the following property of (xr , yr ).
Lemma 5. The edge (xr , yr ), which is a back edge, always exists and when used for r traversal
satisfies A1 and A2 .
Proof. Existence of (x2 , y2 ) clearly implies the existence of (xr , yr ). Further, (xr , yr ) is a back edge
since both choices for it are back edges, i.e., (x2 , y2 ) (see remark in Scenario 2) and (x02 , y20 ) (as
root(τp ) 6= vL ).
Now, consider the r traversal using (xr , yr ), which produces an untraversed path, say p0 =
path(par(vl ), yr )\{yr }. To prove that this traversal produces only components of type C1 and C2
(hence satisfies A1 ), we only need to prove that any eligible subtree (subtree hanging from p∗R with
an edge to pc ) is not connected to p0 . This is because p0 itself is not connected directly to pc by an
13

edge (as x2 ∈
/ pc ). Now, the only such subtrees not queried while computing (x2 , y2 ) is τp , which
is queried while computing (x02 , y20 ). Hence for either choice for (xr , yr ) ((x2 , y2 ) or (x02 , y20 )), no
eligible subtree will be connected to p0 (ensuring A2 ).
Thus, Lemma 5 ensures that our traversal can follow p∗R as shown in Figure 4 (c). To verify
the third condition of applicability lemma, we find the new root for the component having path pc
as follows. We find the lowest edge on p∗R from pc and the eligible subtrees hanging from p∗R , say
(x3 , y3 ), where y3 ∈ p∗R . In case this edge satisfies A3 , we perform this traversal.
Using Lemma 4 we shall describe the conditions when this edge satisfies applicability lemma.
The choice of (xr , yr ) ensures that either xr ∈ T (vP ) (see Remark in p traversal) or xr ∈ τp (recall
the computation of (x02 , y20 )). Further, using Lemma 5 our r traversal satisfies A1 and A2 . the first
two conditions of applicability lemma. Thus, using Lemma 4 the scenario is not applicable only in
the special case where τd = τp and p∗R traverses τd . Refer to Procedure Heavy-DFS in Appendix A
for the pseudo code of this traversal.
We now present the conditions of the special case and present an overview of how it can be
handled. Since τd = τp , p∗R would traverse τd only if xr ∈ τd = τp , i.e., (xr , yr ) = (x02 , y20 ). Thus,
both the lowest and the highest edges on path(rc , r0 ), i.e., (xp , yp ) and (xr , yr ), from an eligible
subtree hanging from path(vL , vH ) belong to τd . Moreover, since τd hangs from path(vL , vH ), it
does not contain T (vH ). This ensures that if modified r0 traversal is performed ignoring τd , it can
be followed by a disconnecting traversal of τd described as follows.

Special case of heavy subtree traversal
In this section (xp , yp ) and (xr , yr ) correspond to the back edges used in p and r traversals described
earlier, whereas (xr0 , yr0 ) corresponds to the back edge used in modified r0 traversal described below.
We now recall the conditions leading to the special case, and describe its implications on (xp , yp ),
(xr , yr ) and (xd , yd ).
Lemma 6. The conditions of the special case are (i) x3 ∈ T (vR ), (ii) xp ∈ τd , and (iii) (xr , yr ) =
(x02 , y20 ). Following are the properties of (xp , yp ) and (xd , yd ) in this case.
1. yd = yp ,y3 is lower than yd on path(rc , r0 ), and yr is lower than y2 on path(rc , r0 ).
2. No subtree of τd hanging from path(root(τd ), xp ), with an edge to pc , has an edge lower than
y2 on path(rc , r0 ).
3. No subtree of τd hanging from path(root(τd ), xr ), with an edge to pc , has an edge higher than
y3 on path(rc , r0 ).
Proof. Recall the choice of (xd , yd ) and (xp , yp ) (see Section 4.4), it was the highest edge from τd on
path(rc , r0 ) and (xp , yp ) was computed such that yp ∈ path(yd , r0 ). Hence, if xp ∈ τd we necessarily
have yd = yp . Also, y3 is strictly lower than yp (or yd ) else having a lower LCA(x3 , vH ) than
LCA(xp , vH ), (x3 , y3 ) would have been selected as (xp , yp ) earlier. Finally, y2 is strictly higher
than yr otherwise (x2 , y2 ) would have been selected as (xr , yr ) earlier. Second property holds
since (x2 , y2 ) (where x2 ∈ T (vP )) was the lowest edge on path(rc , r0 ) from the eligible subtrees
after p traversal. Third property holds since (x3 , y3 ) (where x3 ∈ T (vR )) was the highest edge on
path(rc , r0 ) from the eligible subtrees after r traversal.
To handle this special case, we revisit the scenario corresponding to r traversal ignoring the
eligible subtree τd . Hence, we choose (xr0 , yr0 ) = (x2 , y2 ) despite having a lower edge (xr , yr ). Now,
based on the lowest edge from component containing pc on the traversed path, we append simple
traversals to this modified r0 traversal in order to satisfy A1 . We shall shortly see that in these
traversals the conditions A2 and A3 are implicitly true.
14

r0

r0
y
pc

yp

r0

0

y
pc

yp

0

pc

yp
y2

y2

p1

p01

yr

yr
x0

yr∗

p01

y2

x0

xτ 0

yr

yτ 0
vl

vL

vP

rc
xr

x 2 vH

xp

(a)

vl

vL

vP

rc
xr

x 2 vH

xp

(b)

vl

vL

vP

rc
xr

xp

x∗r

x 2 vH

(c)

Figure 5: The three traversals for special case of Heavy Subtree Traversal (shown using blue dotted
lines) followed by a modified r0 traversal (shown using blue dashed lines). (a) Root traversal of τd ,
(b) Upward cover traversal of p1 through τ 0 , and (c) Downward cover traversal of p1 using a direct
edge (x0 , y 0 ).

Modified r0 traversal
Consider a modified r0 traversal using (xr0 , yr0 ) = (x2 , y2 ) traversing the path shown in Figure 5
(a), where p∗R0 = path(rc , x2 ) ∪ (x2 , y2 ) ∪ path(y2 , r0 ). This leaves an untraversed part of path(rc , r0 ),
i.e., path(par(vl ), y2 )\{y2 } (say p1 ). Using Lemma 6 we know that y2 is strictly higher than yr
ensuring yr ∈ p1 . Now, the computation of (x2 , y2 ) ensures that no eligible subtree (except for τd )
is connected to both paths p1 , as well as ensuring the lowest edge on p∗R0 from an eligible subtree
is from τd , i.e., (xd , yd ). This implicitly satisfies A2 and A3 , if the appended traversal does not
traverse any part of T (vR0 ) or pc . However, since τd is connected to two paths p1 and pc (violating
A1 ), we need to append p∗R0 with another traversal which disconnects the unvisited part of τd from
the unvisited part of p1 .
Now, the only eligible subtree having an edge to p1 is τd . Still the lowest edge on p∗R0 from
the component having pc may not be from τd . This is because p1 and subtrees connected to it are
also in the component containing pc (since τd has an edge on p1 ). Thus, depending on the lowest
edge on p∗R0 from the component containing pc , say (x, y) with y ∈ p∗R0 , we have three cases (see
Figure 5). If x ∈ τd , we simply perform a root traversal of τd exploiting property 2 of Lemma 6
to disconnect τd and p1 . On the other hand if x ∈ p1 or some subtree connected to p1 , we shall
perform a cover traversal of p1 , which visits all vertices on p1 that are connected to τd . As a result,
the unvisited part of p1 is disconnected from τd . Since yr is the lowest edge from τd on p1 , in case x
is lower than yr on p1 , we simply traverse upwards covering yd and other endpoints of edges from
τd incident on p1 . Else we traverse downwards after making sure that no endpoints of edges from
τd that incident on p1 are above x.
Root Traversal of τd
In this case the lowest edge from component containing pc on p∗R0 is from τd , i.e., (xd , yd ). The
traversal of p∗R0 is followed by the traversal of pR0 = (yp , xp ) ∪ (xp , root(τd )) as shown in Figure 5
(a). Hence, using property 2 in Lemma 6, no subtree of τd hanging from pR0 is connected to pc
(satisfying A1 ). As described earlier, since T (vR0 ) does not have an edge to τd , after the traversal
of p∗R0 ∪ pR0 , the component having pc would have the new root in τd or pc (satisfying A3 ).

15

Cover traversal of p1
In this case the lowest edge from component containing pc on p∗R0 is from p1 (say (x0 , y 0 )) or some
subtree τ 0 (say (yτ 0 , y 0 )) which is connected to p1 , where y 0 ∈ p∗R0 . If connected through τ 0 , we
choose the highest edge (x0 , xτ 0 ) from τ 0 on p1 , with x0 ∈ p1 . If x0 is lower than yr , we perform the
upward traversal towards y2 . Other wise we perform the downward traversal towards vl . In case of
upward traversal, when connected through tau0 , we update (x0 , xτ 0 ) to be the lowest edge from τ 0
on p1 , which still maintains x0 to be lower than yr . Note that this choice of (x0 , xtau0 ) ensures that
path(ytau0 , xtau0 ) is a disconnecting traversal of τ 0 from p1 in both upward and downward traversals.
We also define this path from y 0 to x0 as pτ 0 , i.e., when connected through τ 0 (see Figure 5 (b)), we
have pτ 0 = (y 0 , yτ 0 ) ∪ path(yτ 0 , xτ 0 ) ∪ (xτ 0 , x0 ). Otherwise, in case of direct edge (see Figure 5 (c)),
we have pτ 0 = (y 0 , x0 ).
1. Upward traversal on p1
In case x0 is lower than yr , the traversal of p∗R0 is followed by the traversal of pR0 = pτ 0 ∪
path(x0 , y2 )\{y2 } as shown in Figure 5 (b). Since pR0 is a disconnecting traversal of τ 0 from
p1 , the unvisited part of p1 , say p01 , is not connected to the unvisited part of τ 0 . Also, p01 is
not connected to τd and hence the component containing pc as yr ∈
/ p01 . Since the unvisited
0
part of τ is also not connected to pc , A1 is satisfied. As described earlier, the component
having pc will have the new root in τd , being the only part of the component connected to
pR0 . Since τd is not a heavy subtree, A3 is also satisfied.
2. Downward traversal on p1
In case x0 is higher than yr and we follow the traversal downwards, path(x0 , y2 )\{y2 } might
still have edges from τd . Hence, we modify the traversal of p∗R0 as follows. Let the lowest
edge on path(x0 , y2 ) \ {x0 , y2 } from τd be (x∗r , yr∗ ), where yr∗ ∈ p1 . In case (x∗r , yr∗ ) doesn’t
exist, we simply choose (x∗r , yr∗ ) = (x2 , y2 ). We now perform a modified r00 traversal using
(xr00 , yr00 ) = (x∗r , yr∗ ) traversing the path p∗R00 = path(rc , x∗r ) ∪ (x∗r , yr∗ ) ∪ path(yr∗ , r0 ) as shown
in Figure 5 (c). Since yr∗ is higher than x0 , again the path from lowest edge on p∗R00 from
the component containing pc , to p1 would correspond to pτ 0 . This traversal is then followed
by the traversal of pR00 = pτ 0 ∪ path(x0 , par(vl )) as shown in Figure 5 (c). Since pR00 is a
disconnecting traversal of τ 0 from p1 , the unvisited part of p1 , say p01 , is not connected to the
unvisited part of τ 0 . Also, p01 would not be connected to τd and hence component containing
pc , because yr∗ was the lowest edge above x0 on p1 from τd . Since the unvisited part of τ 0 is
not connected to pc , A1 is satisfied. As described earlier, the component having pc will have
the new root in τd , being the only part of the component connected to pR0 . Since τd is not a
heavy subtree, A3 is also satisfied.
Thus, in all the cases of Special Case of heavy path traversal, one of the traversals described
above is necessarily applicable. Refer to Procedure Heavy-Special in Appendix A for pseudo code.

Correctness:
To prove the correctness of our algorithm, it is sufficient to prove two properties. Firstly, the
components property is satisfied in each traversal mentioned above. Secondly, every component in
a phase/stage, abides by the size constraints defining the phase/stage. By construction, we always
choose the lowest edge from a component to the recently added path in T ∗ ensuring that the
components property is satisfied. Furthermore, in the different traversals we have clearly proved
how the stage/phase is progressed ensuring the size constraints. Thus, the final tree T ∗ returned
by the algorithm is indeed the DFS tree of the updated graph.
16

Analysis
We now analyze a stage of the algorithm for processing a component c. In each stage, our algorithm
performs at most O(1) traversals of each type described above. Let us first consider the queries
performed on the data structure D. Every traversal described above performs O(1) sets of these
queries sequentially, where each set may have O(|c|) parallel queries (refer to Appendix A for the
pseudo code). Moreover, each of these sets is an independent set of parallel queries on D (recall the
definition of independent queries in Section 2). This is because in each set of parallel queries, different queries are performed either on different untraversed subtrees of currently processed subtree
or on the traversed path in the currently processed subtree. The remaining operations (excluding
queries to D) clearly requires only the knowledge of the current DFS tree T (and not whole G).
Hence, they can be performed locally in the distributed and semi-streaming environment. Performing these operations efficiently in parallel shall be described in Section 5. Since our algorithm
requires log n phases each having log n stages, we get the following theorem.
Theorem 3. Given an undirected graph and its DFS tree T , any subtree τ of T can be rerooted at
any vertex r0 ∈ τ by sequentially performing O(log2 n) sets of O(|τ |) independent queries on D, in
addition to local computation requiring only the subtree τ .

5

Implementation in the Parallel Environment

We assign |c| processors to process a component c, requiring overall n processors. We first present
efficient implementation of D and the operations on T used by our algorithm.

5.1

Basic Data Structures

The data structure maintained by our algorithm uses the following classical results for finding the
properties of a tree on an EREW PRAM.
Theorem 4 (Tarjan and Vishkin [50]). A rooted tree on n vertices can be processed in O(log n) time
using n processors to compute post order numbering of the tree, level and number of descendants
for each vertex on a EREW PRAM.
Theorem 5 (Schieber and Vishkin [41]). A rooted tree on n vertices can be preprocessed in O(log n)
time using n processors on an EREW PRAM such that k LCA queries can be answered in O(1)
time using k processors on a CREW PRAM.
Using the standard simulation model [27] for converting a CRCW PRAM algorithm to EREW
PRAM algorithm at the expense of extra O(log n) factor in the time complexity, we get the following
theorem.
Theorem 6. A rooted tree on n vertices can be preprocessed in O(log n) time using n processors on
an EREW PRAM such that any k LCA queries can be answered in O(log n) time using k processors
on an EREW PRAM.
We also use the following classical result to sort and hence report maximum/minimum of a set
of n numbers on an EREW PRAM.
Theorem 7 (Cole [12, 13]). A set of n numbers can be sorted using parallel merge sort in O(log n)
time using n processors on an EREW PRAM.

17

5.2

Implementation of D

Given the DFS tree T of the graph, we build the data structures described in Theorem 4 and
Theorem 6 on it. Now, given the post order traversal of T , we assign each vertex with a value equal
to its rank in the post order traversal. Now, for each vertex v we perform a parallel merge sort on
the set of neighbors of the vertex using degree(v)
processors, requiring overall m processors. Thus,

each vertex stores its neighbors say N (v) in the increasing order of their post order indexes. Due
to absence of cross edges in a DFS tree T , the neighbors of every vertex would be sorted in the
order they appear on the path from root(T ) to the vertex. Thus, the data structure D can be built
in O(log n) time (for sorting) using m processors on an EREW PRAM. This allows us to answer
the following queries efficiently.

1. Query w, path(x, y) : among all the edges from w that are incident on path(x, y) in G, return
an edge that is incident nearest to x on path(x, y).

2. Query T (w), path(x, y) : among all the edges from T (w) that are incident on path(x, y) in
G, return an edge that is incident nearest to x on path(x, y).

3. Query path(v, w), path(x, y) : among all the edges from path(v, w) that are incident on
path(x, y) in G, return an edge that is incident nearest to x on path(x, y).
We now describe how to perform a set of independent queries to D (recall definition of independent queries in Section 2) in O(log n) time on an EREW PRAM as follows. We assign one
processor for each vertex u ∈ {w}, T (w) or path(x, y) (depending on the type of query) to perform
the following in parallel. For the vertex u, we would first perform a binary search for the range
given by the post order indexes of x and y on N (u) to find the required edge. However, since all
vertices of path(x, y) may not be ancestors of u, N (u) may include some edges not on path(x, y)
too in the given range, corrupting the search results. Hence, the search would be performed on
a modified range described as follows. Firstly, assuming x is an ancestor of y, if LCA(u, x) is
not equal to x the search would not be performed (as x is not an ancestor of u). Otherwise, the
search is performed on the range given
by post order indexes of x and LCA(u, y). However, in

case of Query path(v, w), path(x, y) we surely know that no vertex of path(v, w) is a descendant
of path(x, y) (recall its definition in Section 2). Thus, we reverse the roles of the paths taking
maximum or minimum accordingly using |path(x, y)| processors. Thus, each of these queries would
require O(log n) time on an EREW PRAM. Now, given a set of independent queries on D, each
processor shall be using different N (u) for finding the corresponding edge. Hence, all the queries
can be performed simultaneously on different memory cells abiding the constraints of an EREW
PRAM. Now, the highest or lowest edge among all the edges returned by different processors can
be found by taking the maximum or minimum in O(log n) time on an EREW PRAM (Theorem 7).
Thus, we have the following theorem.
Theorem 8. The DFS tree T of a graph can be preprocessed to build a data structure D of
size O(m) in O(logn) time using m processors
 such that a set of independent queries of types
Query w, path(x, y) , Query T (w), path(x, y) and Query path(v, w), path(x, y) on T can be answered simultaneously in O(log n) time using 1, |T (w)| and |path(x, y)| processors respectively on
an EREW PRAM.
Extension to handle multiple updates
Consider a sequence of k updates on graph, let Ti∗ represent the DFS tree computed by our algorithm
after i updates in the graph. We also denote the corresponding data structure D built on Ti∗ as
18



Di . We now show that any query
of the type Query w, path(x, y) , Query Ti∗ (w), path(x, y) and

Query path(v, w), path(x, y) on Di , can be performed on D0 if path(x, y) is an ancestor-descendant
path in T . Recall that each such query is performed by querying the N (x) corresponding to each
descendant vertex x separately, whose results are later combined. Thus, even if Ti∗ (w) is not a
subtree of T or path(v, w) is not an ancestor-descendant path of T , it does not affect the processing
of the query, as long as path(x, y) is an ancestor-descendant path of T .
The only extra procedure to be performed to answer such queries correctly using D0 , is to
update the N (x) for any vertex x whose adjacency list is affected by the graph update. For
insertion/deletion of a vertex x, we simply add/delete the corresponding list N (x). For insertion of
vertex we additionally sort it according to post order traversal of T using n processors in O(log n)
time. Note that we do not need to update the N (y) for each neighbor y of x, as the query path
being an ancestor-descendant path of both Ti∗ and T would not contain x. However, on insertion of
a vertex x, such a query can be made with the entire path representing only x. Hence, we assign the
highest post order number to x, and add it to the end of N (y) for each neighbor y of x. This can
be done using n processors in O(1) time on an EREW PRAM. Insertion/deletion of single edges
can be taken care of individually by each search procedure taking O(log n + k) time to perform
search after k updates. Thus, we have the following theorem
Theorem 9. The data structure D built on the DFS tree T of a graph G, can be used to perform

a set of independent queries on Dk of types Query w, path(x, y) , Query Tk∗ (w), path(x, y) and
Query path(v, w), path(x, y) , in O(log n + k) time using 1, |Tk∗ (w)| and |path(x, y)| processors
respectively on an EREW PRAM, if path(x, y) is an ancestor-descendant path of T .

5.3

Implementation of operations on T

As described earlier several properties of T can be reported in O(1) time using the data structures
described in Theorem 4 and Theorem 6.
1. Determine whether an edge (x, y) is a back edge in T
This query can easily be answered by finding l = LCA(x, y). If l = x or l = y the edge (x, y)
is a back edge in T . Hence, reporting whether an edge is a back edge can be reduced to
finding LCA of two vertices in T .
2. Finding length of a path
Compare the level of the two end points as reported by structure in Theorem 4.
3. Given x ∈ T (y), find child y 0 of y such that x ∈ T (y 0 )
For each vertex v of the graph perform the following in parallel (using |T (y)| processors), if
par(v) is y and LCA(v, x) is v then report v. This query too reduces to finding LCA of two
vertices in T .
4. Determine whether x lies on path(y, z), where y is ancestor of z
If LCA(x, z) = x and LCA(x, y) = y, then x lies on path(y, z).
5. Subtrees hanging from a path(x, y)
For each vertex v of the graph perform the following in parallel (using total n processors), if
LCA(v, y) = par(v) then T (v) is a subtree hanging from the path.
The number of processors required for the last three queries is equal to the size of the corresponding component, remaining queries requiring a single processor each. Thus, using Theorem 7
and procedures described above we have the following theorem
19

Theorem 10. The DFS tree T of a graph can be preprocessed to build a data structure of size
O(n) in O(log n) time using n processors such that following queries can be answered in parallel in
O(log n) time on an EREW PRAM
• LCA of two vertices, size of a subtree, testing if an edge is back edge and length of a path
using a single processor per query.
• Finding vertices on a path, subtrees hanging from a path, child of a vertex containing a given
vertex, highest/lowest edge among k edges, using k processors per query, where k is the size
of the corresponding component.

5.4

Analysis

Using these data structures we can now analyze the time required by the reduction algorithm on
an EREW PRAM. Since the queries on D and LCA queries on T can be answered in O(log n) time
using n processors as described above, Theorem 2 reduces to the following theorem.
Theorem 11. Given the DFS tree T of a graph and the data structure D built on it, any update
on the graph can be reduced to independently rerooting disjoint subtrees of the DFS tree using n
processors in O(log n) time on an EREW PRAM.
Implementation details
All operations required for each stage of our rerooting algorithm to reroot a subtree τ , can be
performed in O(log n) time using |τ | processors using Theorem 8 and Theorem 10 as follows. Both
root(τc ) and vertex vH required by our algorithm while processing a component c can be computed
in parallel by comparing the size of each subtree using |c| processors. Adding a path p to T ∗
essentially involves marking the corresponding edges as tree edges, which can be performed by
informing the vertices on p. All the other operations of the rerooting algorithm (refer to pseudo
code in Appendix A) are trivially reducible to the operations described in Theorem 10. Since our
rerooting algorithm requires log n phases each having log n stages, we get the following theorem for
rerooting disjoint subtrees using our rerooting algorithm.
Theorem 12. Given an undirected graph with the data structure D build on its DFS tree, independently rerooting disjoint subtrees of the DFS tree can be performed in O(log3 n) time using n
processors on an EREW PRAM model.
Using Theorem 11, Theorem 12 and Theorem 8, we can prove our main result as follows.
Theorem 1. Given an undirected graph and its DFS tree, it can be preprocessed to build a data
structure of size O(m) in O(log n) time using m processors on an EREW PRAM such that for any
update in the graph, a DFS tree of the updated graph can be computed in O(log3 n) time using n
processors on an EREW PRAM.
Now, in order to prove our result for Parallel Fully Dynamic DFS and Parallel Fault Tolerant
DFS we need to first build the DFS tree of the original graph from scratch during preprocessing
stage. This can be done using the static DFS algorithm [47] or any advanced deterministic parallel
algorithm [1, 22]. Thus, for processing any update we always have the current DFS tree built
(either originally during preprocessing or by the update algorithm). We can thus build the data
structure D using Theorem 8 reducing Theorem 1 to the following theorem.

20

Theorem 13 (Parallel Fully Dynamic DFS). Given an undirected graph, we can maintain its DFS
tree under any arbitrary online sequence of vertex or edge updates in O(log3 n) time per update
using m processors in parallel EREW model.
However, if we limit the number of processors to n, our fully dynamic algorithm cannot update
the DFS tree in Õ(1) time, only because updating D in Õ(1) time requires O(m) processors (see
Theorem 8). Thus, we build the data structure D using Theorem 8 during preprocessing itself, and
attempt to use it to handle multiple updates.

Extending to multiple updates
Consider a sequence of k updates on graph, let Ti∗ represent the DFS tree computed by our algorithm
after i updates in the graph. We also denote the corresponding data structure D built on Ti∗ as Di .
Now, consider any stage of our algorithm while building the DFS tree Ti∗ . For each component in
∗
parallel, O(1) ancestor-descendant paths of Ti−1
are added to Ti∗ . Thus, any ancestor-descendant
2
∗ , corresponding to O(log n) phases
path p of Ti∗ , is built by adding O(log n) such paths of Ti−1
2
∗ , say
each having O(log n) stages. Hence, p is union of O(log n) ancestor-descendant paths of Ti−1
p1 , ..., pk .
Using this reduction, it can be shown that a set of independent queries on path p in Di , can be
reduced to O(log2 n) sets of independent queries on corresponding O(log2 n) paths p1 , ..., pk on Di−1
∗ ,
(see Section 5.2). Again, each of these paths p1 , ..., pk , being an ancestor-descendant path of Ti−1
∗ , and so on. Thus, any set of independent
is a union of O(log2 n) ancestor-descendant paths of Ti−2
queries on Di can be performed by O(log2(i−1) n) sets of independent queries on D, which takes
O(log2i−1 ) time on an EREW PRAM using n processors when k ≤ log n (see Theorem 8 and
∗
Section 5.2). The other data structures on Ti−1
can be built in O(log n) time using n processors
∗
(see Theorem 10). This allows our algorithm to build the DFS tree Ti∗ from Ti−1
using D in
2i+1
O(log
) time on an EREW PRAM using n processors (see Theorem 3). Thus, for a given set of
∗
k updates we build each Ti∗ one by one using Ti−1
and D, to get the following theorem.
Theorem 14 (Parallel Fault Tolerant DFS). Given an undirected graph, it can be preprocessed to
build a data structure of size O(m) such that for any set of k (≤ log n) updates in the graph, a DFS
tree of the updated graph can be computed in O(k log2k+1 n) time using n processors on an EREW
PRAM.
Remark. For k = 1, our algorithm also gives an O(n log3 n) time sequential algorithm for updating
a DFS tree after a single update in the graph, achieving similar bounds as Baswana et al. [6].
However, our algorithm uses much simpler data structure D at the cost of a more complex algorithm.

6

Applications in other models of computation

We now briefly describe how our algorithm can be easily adopted to the semi-streaming model and
distributed model.

6.1

Semi-Streaming Setting

Our algorithm only stores the current DFS tree T and the partially built DFS tree T ∗ taking O(n)
space. Thus, all operations on T can be performed without any passes over the input graph. A set
of independent queries on D is evaluated by performing a single pass over all the edges of the input
graph using O(n) space. This is because each set has O(n) queries (see Theorem 2 and Theorem 3)
and we are required to store only one edge per query (partial solution based on edges visited by
21

the pass). Note that here the role of D is performed by a pass over the input graph. Hence,
the algorithm is first executed for all the components in turn until each instance of the algorithm
queries the data structure D. This is followed by a pass on the input graph to answer these queries
and so on. Since each stage requires O(1) steps (and hence O(1) sequential queries on D), it can
be performed using O(1) passes. Thus, our algorithm requires O(log2 n) passes to update the DFS
tree after a graph update by executing log n stages for each of the log n phases. Thus, we get the
following theorem.
Theorem 15. Given any arbitrary online sequence of vertex or edge updates, we can maintain
a DFS tree of an undirected graph using O(log2 n) passes over the input graph per update by a
semi-streaming algorithm using O(n) space.

6.2

Distributed Setting

Our algorithm stores only the current DFS tree T and the partially built DFS tree T ∗ at each
node. Thus, the operations on T are performed locally at each node and the distributed computation is only used to evaluate the queries on D. Using Theorem 2 and Theorem 3, each update is
performed by O(log2 n) sequential sets of O(n) independent queries on D. Evaluation of a set of
O(n) independent queries on D can be essentially reduced to propagation of O(n) words (partial
solutions of n queries) throughout the network. Using the standard technique of pipelined broadcasts and convergecasts [38], we can propagate these O(n) words in O(D) rounds using messages
of size O(n/D). This proves our distributed algorithm described in Section 1.2. We now describe
the implementation details in the distributed model.
Implementation in distributed environment
We now present how our algorithm can be implemented on the distributed model. In the synchronous CON GEST (B) model a processor is present at every node of the graph and communication links are restricted to the edges of the graph. The communication occurs in synchronous
rounds, where each nodes can send a message of O(B) words along each communication link. Our
model includes a preprocessing stage followed by an alternating sequence of update and recovery
stages. The graph is updated in the update stage, after which the recovery stage starts in which
the algorithm updates the DFS tree of the graph. The model allows the algorithm to complete
updating the DFS tree (completing the recovery stage) before the next update is applied to the
graph (update stage). Similar model was earlier used by Henzinger et al. [25]. We use an additional
constraint of a space restriction of O(n) size at each node. In the absence of this restriction, the
whole graph can be stored at each node, where an algorithm can trivially propagate the update to
each node and the updated solution can be computed locally. Finally, we also allow the deletion
updates to be abrupt, i.e., the deleted link/node becomes unavailable for use instantly after the
update.
Each node stores the current DFS tree T and the partially built DFS tree T ∗ . Thus, all the
operations on T can be performed locally at each node, where the distributed computation is used
only to evaluate the queries on D. Also, using Theorem 2 and Theorem 3 each update reduces to
O(log2 n) sequential sets of O(n) independent queries on D. Thus, we shall only focus on how to
evaluate such queries efficiently in the distributed environment.
6.2.1

Optimality of message size

We first prove that any distributed algorithm maintaining the DFS tree at each node requires a
message size of Ω(n/D) to update the DFS tree in O(D) rounds. Consider the insertion of a vertex,
22

such that the final DFS tree uses O(n) of the newly inserted edges. This is clearly possible if the
current DFS tree has O(n) branches, where leaf of each branch is connected to the inserted vertex.
Thus, the information of at least these O(n) new edges needs to be propagated throughout the
network by any algorithm maintaining DFS tree at each node. Now, broadcasting m messages on a
network with diameter D requires Ω(m + D) rounds [38]. In order to limit the number of rounds to
O(D), we can send only O(D) messages. Thus, any algorithm sending O(n) words of information
using O(D) messages would require a message size of Ω(n/D). We thus use the CON GEST (n/D)
model for our distributed algorithm.
6.2.2

Evaluation of queries on D

Now, each node only stores the adjacency list of the corresponding vertex in addition to T and T ∗
described above. Recall that a query on D is merely highest/lowest edge among a set of eligible
edges. Hence, it can be easily evaluated for the whole graph by combining the partial solutions
of the same query performed on each adjacency list locally at the node. Thus, the focus is to
broadcast the partial solution from each node to reach the whole graph, where each node can then
combine them locally to get the solution to the query. Moreover, these partial solutions can also
be combined during broadcasting itself to avoid sending too many messages as described below.
Performing broadcasts efficiently
Broadcasts can be performed efficiently by using a spanning tree of the graph. To ensure efficiency
of rounds we use a BFS tree as follows. After every update, any vertex (say vertex with the smallest
index) starts building a BFS tree B rooted at it. The depth of B is O(D) and it can be built in O(D)
rounds using O(m) messages [38]. All the broadcasts are now performed only on the tree edges of
B as follows. We first describe it for a single query then extend it to handle O(n) queries. Note
that it is a trivial extension of the standard pipelined broadcasts and convergecasts algorithm [38].
Each node waits for partial solutions to the query from all its children in B, updates its solution and
sends it to its parent. On receiving the partial solutions from all the children, the root computes
the final solution and sends it back to all nodes along the tree edges of B. Clearly, this process
requires O(D) rounds and O(n) messages each of size O(1) (partial solution of a query is a single
edge). In order to perform O(n) independent queries efficiently in parallel, on each edge we send
D messages of size O(n/D) in a pipelined manner (one after the other) to achieve the broadcast in
O(D) time (see pipelined broadcast in [38]). The total number of messages sent would be O(nD).
Since the rerooting algorithm requires O(log2 n) sequential sets of O(n) queries (see Theorem 3),
we get the following theorem.
Theorem 16. Given any arbitrary online sequence of vertex or edge updates, we can maintain a
DFS tree in O(D log2 n) rounds per update in a distributed setting using O(nD log2 n+m) messages
each of size O(n/D) and O(n) local space on each processor, where D is diameter of the graph.
Remark. Our initial assumption of adding a pseudo root (see Section 2) connected to every vertex
of the graph is no longer valid in the distributed system. This is because both the processors and
communication links are fixed in our model. Thus, we need to maintain a DFS forest instead of a
DFS tree requiring to handle the cases when some component is partitioned into several components
and when two or more components merge as a result of a graph update. The following section
describes how this can be achieved in the same bounds described above.

23

Maintaining a DFS forest
After every update in the graph, a neighboring vertex of the affected link/node shall broadcast
the information about the update to all the vertices in the component. However, in order to limit
the number of messages transmitted, exactly one vertex from each component so formed needs to
initiate the broadcast. We shall shortly describe how to choose this vertex. The chosen vertex also
chooses the new root for the DFS tree of the component (say the node with the smallest index). The
new root then makes the corresponding BFS tree as described above to perform efficient broadcasts.
In case two or more components are merged due to the update, the DFS tree of each component
computed earlier is broadcasted to the entire component by the original roots of two components.
Since, the size of broadcast (DFS tree) is O(n), it can be performed under the same bounds as
described above.
We now describe how to choose the broadcast vertex efficiently. In case of vertex/edge insertion,
we choose the inserted vertex or endpoint of the inserted edge with smaller index respectively. In
case of vertex/edge deletion, for each component so formed, we choose the neighbor of deleted
node/link in T that has the smallest index. For this each neighbor of the deleted node/link needs
to know the resultant components formed as a result of the deletion. This can be easily computed
locally if each node also stores the articulation points/bridges of the current DFS tree T . Hence,
after computing the DFS tree, each node computes the articulation points/bridges of the DFS tree
according of the subgraph induced by the edges of T and the adjacency list stored at the node.
The vertices/edges present in all the sets of articulation points/bridges computed at different nodes
will be the articulation points/bridges of the whole graph. Again, this requires each vertex to send
O(n) words of information where the partial solutions can be combined. Thus, it can be performed
similar to the queries on D using the same bounds.

7

Conclusion

Our parallel dynamic algorithms take nearly optimal time on an EREW PRAM. However, the work
efficiency of our fully dynamic algorithm is Õ(m) whereas that of the best sequential algorithm [7]
√
is Õ( mn). Even though our fault tolerant algorithm is nearly work optimal, its only for constant
number of updates. The primary reason behind these limitations is the difficulty in updating the
data structure D using n processors. Our fault tolerant algorithm avoids updating D, by naively
using the original D to simulate the queries of updated D. It would be interesting to see if an
algorithm can process significantly more updates using only n processors in Õ(1) time (similar
extension was performed by Baswana et al. [7] in the sequential setting). This may also lead to a
fully dynamic algorithm that is nearly time optimal with better work efficiency.
Further, our distributed algorithm works only on a substantially restricted synchronous CON GEST (n/D)
model. Moreover, the number of messages passed during an update in the distributed algorithm is
O(nD log2 n + m), which is way worse than the number of messages required to compute a DFS
from scratch i.e. O(n). It would be interesting to see if dynamic DFS can be maintained in near
optimal rounds in more stronger CON GEST or LOCAL models.

Acknowledgement
I am grateful to Christoph Lenzen for suggesting this problem. I would also like to express my
sincere gratitude to my advisor Prof. Surender Baswana for valuable discussions and key insights
that led to this paper. The idea of extending the parallel algorithm to the distributed setting was
rooted in these discussions. Finally, I would like to thank the anonymous reviewers and my advisor
whose reviews significantly helped me to refine the paper.
24

References
[1] Alok Aggarwal and Richard J. Anderson. A random NC algorithm for depth first search.
Combinatorica, 8(1):1–12, 1988.
[2] Alok Aggarwal, Richard J. Anderson, and Ming-Yang Kao. Parallel depth-first search in
general directed graphs. SIAM J. Comput., 19(2):397–409, 1990.
[3] Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with
application to the maximum matching problem. Inf. Comput., 222:59–79, 2013.
[4] Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in
dynamic graph streams and the simultaneous communication model. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1345–1364, 2016.
[5] Baruch Awerbuch, Israel Cidon, and Shay Kutten. Optimal maintenance of a spanning tree.
J. ACM, 55(4), 2008.
[6] Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. Dynamic DFS tree in undirected graphs: breaking the O(m) barrier, full version of [7]. CoRR,
abs/1502.02481, 2015.
[7] Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. Dynamic
DFS in undirected graphs: breaking the O(m) barrier. In ACM-SIAM Symposium on Discrete
Algorithms, SODA, pages 730–739, 2016.
[8] Surender Baswana and Keerti Choudhary. On dynamic DFS tree in directed graphs. In
Mathematical Foundations of Computer Science, MFCS, pages 102–114, 2015.
[9] Surender Baswana and Shahbaz Khan. Incremental algorithm for maintaining DFS tree for
undirected graphs. In ICALP, pages 138–149, 2014.
[10] E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan. An efficient incremental algorithm
for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel
Processing Letters, 10:253–266, 2000.
[11] Israel Cidon. Yet another distributed depth-first-search algorithm.
26(6):301–305, 1988.

Inf. Process. Lett.,

[12] Richard Cole. Parallel merge sort. SIAM J. Comput., 17(4):770–785, 1988.
[13] Richard Cole. Correction: Parallel merge sort. SIAM J. Comput., 22(6):1349, 1993.
[14] Martin E. Dyer and Alan M. Frieze. Probabilistic analysis of a parallel algorithm for finding
the lexicographically first depth first search tree in a dense random graph. Random Struct.
Algorithms, 2(2):233–240, 1991.
[15] Paul Erdős and Alfréd Rényi. On random graphs I. Publicationes Mathematicae (Debrecen),
6:290–297, 1959.
[16] Shimon Even and Robert Endre Tarjan. Network flow and testing graph connectivity. SIAM
J. Comput., 4(4):507–518, 1975.

25

[17] Martin Farach-Colton, Tsan-sheng Hsu, Meng Li, and Meng-Tsung Tsai. Finding articulation
points of large graphs in linear time. In Algorithms and Data Structures, WADS, pages 363–
372, 2015.
[18] P. Ferragina. A technique to speed up parallel fully dynamic algorithms for MST. J. Parallel
Distrib. Comput., 31(2):181–189, December 1995.
[19] Paolo Giulio Franciosa, Giorgio Gambosi, and Umberto Nanni. The incremental maintenance
of a depth-first-search tree in directed acyclic graphs. Inf. Process. Lett., 61(2):113–120, 1997.
[20] Jon Freeman. Parallel algorithms for depth-first search. Technical Report, University of Pennsylvania, October 1991.
[21] Ratan K. Ghosh and G. P. Bhattacharjee. A parallel search algorithm for directed acyclic
graphs. BIT, 24(2):134–150, 1984.
[22] Andrew V. Goldberg, Serge A. Plotkin, and Pravin M. Vaidya. Sublinear-time parallel algorithms for matching and related problems. J. Algorithms, 14(2):180–213, 1993.
[23] Sudipto Guha, Andrew McGregor, and David Tench. Vertex and hyperedge connectivity in
dynamic graph streams. In ACM Symposium on Principles of Database Systems, PODS, pages
241–247, 2015.
[24] Torben Hagerup. Planar depth-first search in O(log n) parallel time. SIAM J. Comput.,
19(4):678–704, 1990.
[25] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks. In ICALP (2), pages
607–619, 2013.
[26] Zengfeng Huang and Pan Peng. Dynamic Graph Stream Algorithms in o(n) Space. In 43rd
International Colloquium on Automata, Languages, and Programming (ICALP 2016), pages
18:1–18:16, 2016.
[27] Joseph JáJá. An Introduction to Parallel Algorithms. Addison-Wesley, 1992.
[28] Junting Jin, Xiaowei Shi, Cuiping Li, and Hong Chen. Fast approximation of shortest path on
dynamic information networks. In Web-Age Information Management WAIM, pages 272–276,
2014.
[29] Ming-Yang Kao. All graphs have cycle separators and planar directed depth-first search is in
DNC. In VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, AWOC,
Proceedings, pages 53–63, 1988.
[30] Valerie King, Shay Kutten, and Mikkel Thorup. Construction and impromptu repair of an
MST in a distributed network with o(m) communication. In Proceedings of the 2015 ACM
Symposium on Principles of Distributed Computing, PODC, pages 71–80, 2015.
[31] Devendra Kumar, S. Sitharama Iyengar, and Mohan B. Sharma. Corrigenda: Corrections to
a distributed depth-first search algorithm. Inf. Process. Lett., 35(1):55–56, 1990.
[32] K. B. Lakshmanan, N. Meenakshi, and Krishnaiyan Thulasiraman. A time-optimal messageefficient distributed algorithm for depth-first-search. Inf. Process. Lett., 25(2):103–109, 1987.

26

[33] Shuang Liu, Brice Effantin, and Hamamache Kheddouci. A fully dynamic distributed algorithm
for a B-coloring of graphs. In IEEE International Symposium on Parallel and Distributed
Processing with Applications, ISPA, pages 657–662, 2008.
[34] S. A. M. Makki and George Havas. Distributed algorithms for depth-first search. Inf. Process.
Lett., 60(1):7–12, 1996.
[35] Andrew McGregor. Graph stream algorithms: A survey. SIGMOD Rec., 43(1):9–20, May
2014.
[36] Thomas C. O’Connell. A survey of graph algorithms under extended streaming models of
computation. In Fundamental Problems in Computing: Essays in Honor of Professor Daniel
J. Rosenkrantz, pages 455–476, 2009.
[37] Chao-Wei Ou and Sanjay Ranka. Parallel incremental graph partitioning. IEEE Trans. Parallel
Distrib. Syst., 8(8):884–896, 1997.
[38] David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and
Applied Mathematics, Philadelphia, PA, USA, 2000.
[39] John H. Reif. Depth-first search is inherently sequential. Inf. Process. Lett., 20(5):229–234,
1985.
[40] Jan Matthias Ruhl. Efficient algorithms for new computational models. PhD Thesis, Department of Computer Science, MIT, Cambridge, MA, 2003.
[41] Baruch Schieber and Uzi Vishkin. On finding lowest common ancestors: Simplification and
parallelization. SIAM J. Comput., 17(6):1253–1262, 1988.
[42] Kirk Schloegel, George Karypis, and Vipin Kumar. Parallel static and dynamic multiconstraint graph partitioning. Concurrency and Computation: Practice and Experience,
14(3):219–240, 2002.
[43] Mohan B. Sharma and S. Sitharama Iyengar. An efficient distributed depth-first-search algorithm. Inf. Process. Lett., 32(4):183–186, 1989.
[44] Deepak D. Sherlekar, Shaunak Pawagi, and I. V. Ramakrishnan. O(1) parallel time incremental
graph algorithms. In Foundations of Software Technology and Theoretical Computer Science,
pages 477–495, 1985.
[45] Justin R. Smith. Parallel algorithms for depth-first searches i. planar graphs. SIAM J. Comput.,
15(3):814–830, 1986.
[46] Bala Swaminathan and Kenneth J. Goldman. An incremental distributed algorithm for computing biconnected components in dynamic graphs. Algorithmica, 22(3):305–329, 1998.
[47] Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput.,
1(2):146–160, 1972.
[48] Robert Endre Tarjan. Finding dominators in directed graphs. SIAM J. Comput., 3(1):62–89,
1974.
[49] Robert Endre Tarjan. Edge-disjoint spanning trees and depth-first search. Acta Inf., 6:171–185,
1976.
27

[50] Robert Endre Tarjan and Uzi Vishkin. Finding biconnected components and computing tree
functions in logarithmic parallel time (extended summary). In 25th Annual Symposium on
Foundations of Computer Science, pages 12–20, 1984.
[51] Yung H. Tsin. Some remarks on distributed depth-first search. Inf. Process. Lett., 82(4):173–
178, 2002.
[52] Y. Zhang. Parallel algorithms for problems involving directed graphs. PhD Thesis, Drexel
University, Philadelphia, PA, 1986.

A

Pseudo codes of Traversals in Rerooting Algorithm

Procedure Reroot-DFS(rc , pc , Tc ): Traversal enters through rc into the component c containing a path pc and set of trees Tc .
*/

4

/* Let current phase be Pi and current stage be Sj
τc ← Heaviest tree in Tc ;
T (vH ) ← Smallest subtree having size at least n/2i ;
if |τc | ≤ n/2i then Return Reroot-DFS(rc , pc , Tc ) in next phase;
if |pc | ≤ n/2j then Return Reroot-DFS(rc , pc , Tc ) in next stage;
/* Disintegrating Traversal
if pc = φ or rc = root(τc ) then Return DisInt-DFS(rc , pc , Tc );

*/

5

/* Disconnecting Traversal
if rc ∈
/ Tc ∪ {pc } or rc ∈ T (vH ) then Return DisCon-DFS(rc , pc , Tc );

*/

6

1
2
3

7
8

if rc ∈ pc then Return Path-Halving(rc , pc , Tc , φ);
Heavy-DFS(rc , pc , Tc ) ;

28

/* Path Halving */
/* Heavy Subtree Traversal */

Procedure Process-Comp(P, T , p∗ ): Moves components created of type C1 and components
created with p ∈ P of type C2 to the next stage, after traversal of p∗ = p1 ∪ p2 ∪ p3 , the newly
added path in T ∗ . Here, p ∈ P, p1 , p2 and p3 are ancestor-descendant paths of T and traversal
of p∗ ensures components of type C1 and C2 with paths in P only.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

foreach p ∈ P do
/* p = path(x, y), where x
foreach τ ∈ T in parallelusing |τ | processors do
if Query τ, path(x, y) 6= φ then
/* ∃ edge
T ← T \ {τ }, Tp ← Tp ∪ {τ };
end
end
for p0 ∈ {p3 , p2 , p1 } do
/* p0 = path(x0 , y 0 ), where x0

{xp , yp } ← Query p, path(x0 , y 0 ) ;
/*

0
0
foreach τ ∈ Tp do (xτ , yτ ) ← Query τ, path(x , y ) ;
/*
{xp , yp } ← Lowest edge on T ∗ among (xp , yp ) and (xτ , yτ ), ∀τ ∈ Tp ;
if (xp , yp ) is a valid edge then break;
end
Add (xp , yp ) to T ∗ ;
Reroot-DFS(xp , p, Tp ) in current stage;
end
foreach τ ∈ T in parallel using |τ | processors do
T ← T \ τ;
for p0 ∈ {p3 , p2 , p1 } do
/* p0 = path(x0 , y 0 ), where x0

0
0
(xτ , yτ ) ← Query τ, path(x , y ) ;
/*
if (xτ , yτ ) is a valid edge then break;
end
Add (yτ , xτ ) to T ∗ ;
Reroot-DFS(xτ , φ, {τ }) in next stage;
end

lower in T ∗ */
from τ to p */

lower in T ∗ */
where xp ∈ p */
where xτ ∈ τ */

lower in T ∗ */
where xτ ∈ τ */

Procedure DisInt-DFS(rc , pc , Tc ): Disintegrating Traversal of a component c having a path
pc and a set of trees Tc through the root rc ∈ τ ∈ Tc , where either |pc | = 0 or rc = root(τ ).
1
2
3
4
5
6
7
8

T (vH ) ← Smallest subtree τ 0 of τ , where |τ 0 |> n/2i ;
T ← Subtrees hanging from path rc , root(τ ) ;
T (vh ) ← Subtree from T containing vH ;
T ← T \ T (vh )∪ Subtrees hanging from path(vh , vH );
Add path(rc , vH ) to T ∗ ;
if |pc | =
6 0 then p ← pc ; T ← T ∪ Tc \τ ;



else p ← path par par(vh ) , root(τ ) ;

Process-Comp {p}, T , path(rc , vH ) ;

/* Component of type C2 */

/* remaining part of path rc , root(τ ) */
/* Goes to DisCon-DFS or next phase */

29

Procedure Path-Halving-DFS(rc , pc , Tc ): Traversal of a component c having a path pc and
a set of trees Tc through the root rc ∈ pc .
1
2
3
4

pc ← pc \ path(rc , x) ;
p∗ ← path(rc , x);
Add p∗ to T ∗ ;

Process-Comp {pc }, Tc , p∗ ;

/* pc = path(x, y) where |path(x, rc )| ≥ |path(y, rc )| */

/* Goes to next stage */

Procedure DisCon-DFS(rc , pc , Tc ): Disconnecting Traversal of a component c having a path
pc and a set of trees Tc through the root rc , where either rc ∈ τ ∈
/ Tc or rc ∈ T (vH ).
1
2
3
4
5
6
7

/* pc = path(u, v), where u is ancestor of v
if τ has an edge to upper half of pc then
(x, y) ← Lowest edge from τ to pc ; p0c ← path(y, u) ;
/* where x ∈ τ
else (x, y) ← Highest edge from τ to pc ; p0c ← path(y, v) ;
/* where x ∈ τ

T ← Subtrees hanging from path rc , root(τ ) ;
T (v) ← Subtree from T containing x;
T ← T \ T (v)∪ Subtrees hanging from path(v, x);




p ← path par par(v) , root(τ ) ;
/* remaining part of path rc , root(τ )

8 p∗
9
10

*/
*/
*/

*/

p0c ;

← path(rc , x) ∪ (x, y) ∪
Add p∗ ) to T ∗ ;

Process-Comp {p, pc \ p0c }, T ∪ Tc \ {τ }, p∗ ;

30

/* Goes to next stage/phase */

Procedure Heavy-DFS(rc , pc , Tc ): Heavy Subtree Traversal of a component c having a path
pc and a set of trees Tc through the root rc ∈ τ ∈ Tc , where r0 = root(τ )
1

2
3
4
5
6
7
8
9

10

11
12
13
14
15
16
17
18
19
20
21
22
23

24

25
26
27
28
29
30
31
32
33
34
35
36
37

38
39

T (vH ) ← Smallest subtree τ 0 of τ , where |τ 0 | > n/2i ;
/* Considering Scenario 1.

T ← Subtrees hanging from path rc , r0 with edge in pc ;
T (vL ) ← Subtree
 from T containing vH ;
p∗ ← path rc , r0 ;
(x1 , y1 ) ← Highest edge to p∗ from τ 0 ∈ T and pc ;

*/

/* where y1 ∈ p∗ */

if x1 ∈
/ T (vL )or x1 ∈ T (vH ) or x1 = vL or x1 ∈ pc then
Add p∗ to T ∗ ;
T ← Subtrees hanging from p∗ ;

Return Process-Comp {pc }, T ∪ Tc \τ, p∗ ;
/* Goes to DisConn, DisInt or Path-Halving
end
/* Considering Scenario 2.
T ← T \ T (vL )∪ Subtrees hanging from path(vL , vH ) with edge in pc ;
(xd , yd ) ← Highest edge to p∗ from τ 0 ∈ T ;
/* where xd ∈ T 0
if (xd , yd ) = φ then yd = rc ;
(xp , yp ) ← {(x0 , y 0 ) : x0 ∈ T (vL ), y 0 ∈ path(yd , r0 ) of minimum LCA(x0 , vH )};

p∗ ← path(rc , xp ) ∪ (xp , yp ) ∪ path yp , par(v
)
;
l

T ← Subtrees hanging from path rc , r0 with edge in pc ;
T ← T \ T (vL )∪ Subtrees hanging from path(vL , xp ) with edge in pc ;
(x2 , y2 ) ← Lowest edge to p∗ from τ 0 ∈ T or pc ;
/* where y2 ∈ p∗
T (vP ) ← The subtree hanging from path(vL , xp ) having vH ;

*/
*/
*/

*/

if x2 ∈
/ T (vP )or x2 ∈ T (vH ) or x2 = vP or x2 ∈ pc then
Add p∗ to T ∗ ;
T ← Subtrees hanging from path(rc , r0 ) and
 path(vL , xp )∗;
0
Return Process-Comp {pc , path par(yp ), r }, T ∪ Tc \τ, p ;
/* Goes to DisConn, DisInt or Path-Halving */
end
/* Considering Scenario 3.
*/
τd ← Subtree hanging on path(vL , vH ) having xd ;
(x02 , y20 ) ← Lowest edge from τd to (rc , yp );
if y2 lower than y20 then (xr , yr ) ← (x02 , y20 );
else (xr , yr ) ← (x2 , y2 );

p∗ ← path(rc , xr ) ∪ (xr , yr ) ∪ path yr , r0 ;
T ← Subtrees hanging from path rc , r0 with edge to pc ;
T ← T \ T (vL )∪ Subtrees hanging from path(vL , xr ) with edge to pc ;
(x3 , y3 ) ← Lowest edge to p∗ from τ 0 ∈ T or pc ;
/* where y3 ∈ p∗ */
T (vR ) ← The subtree hanging from path(vL , xr ) having vH ;
if x3 ∈
/ T (vR )or x3 ∈ T (vH ) or x3 = vP or x3 ∈ pc then
Add p∗ to T ∗ ;
T ← Subtrees hanging from path(rc , r0 ) and
 path(vL , xr ) ;

Return Process-Comp {pc , path par(vl ), yr \ {yr }}, T ∪ Tc \τ, p∗ ;
/* Goes to DisConn, DisInt or Path-Halving */
end
Heavy-Special(rc , pc , Tc );
31

Procedure Heavy-Special(rc , pc , Tc ): Special Case of Heavy Subtree Traversal of a component
c having a path pc and a set of trees Tc through the root rc ∈ τ ∈ Tc .
1
2
3
4
5
6

7
8
9
10
11
12

13

14
15
16
17
18

19
20
21
22
23

24

25
26
27
28
29
30
31
32
33
34
35
36
37
38

/* Modified r0 traversal.
*/

∗
pR0 ← path(rc , x2 ) ∪ (x2 , y2 ) ∪ path y2 , root(τ ) ;
p1 ← path(par(vl ), y2 )\{y2 };

T ← Subtrees hanging from path rc , root(τ ) with edge to p1 ;
T ← T \ T (vL )∪ Subtrees hanging from path(vL , x2 ) with edge to p1 ;
(x0 , y 0 ) ← Lowest edge to p∗R0 from τ 0 ∈ T or p1 ;
/* where y 0 ∈ p∗R0 */
if y 0 at most as high as yp then
/* Root Traversal of τd .
*/
pR0 ← (yp , xp ) ∪ path(xp , root(τd ));
Add p∗R0 and pR0 to T ∗ ;
T ← Subtrees hanging from path(rc , root(τ ))\{T (vL )} ;
T ← T ∪ Subtrees hanging from path(vL , x2 )\{τd } ;
T ← T ∪ Subtrees hanging from path(xd , root(τd ));
Return Process-Comp {pc , p1 }, T ∪ Tc \τ, p∗R0 ∪ pR0
/* Goes to DisConn, DisInt or
Path-Halving */
end
/* Cover traversal of p1
if x0 ∈
/ p1 then
yτ 0 ← x0 ;
{x0 , xτ 0 } ← Highest edge on p1 from τ 0 ;
end

*/
/* Connected to p1 through τ 0 */
/* where x0 ∈ p1 */

if x0 at most as high as yr on p1 then
/* Upward Cover Traversal of p1 .
*/
if xτ 0 6= φ then {x0 , xτ 0 } ← Lowest edge on p1 from τ 0
/* where x0 ∈ p1 */ ;
pR0 ← pτ 0 ∪ path(x0 , y2 )\{y2 };
p01 ← path(par(vl ), x0 )\{x0 };
T ← Subtrees hanging from path(vL , x2 ) ;
else
/* Lower Cover Traversal of p1 .
*/
∗
∗
∗
(xr , yr ) ← Highest edge from τd to path(par(yr ), y2 )\{y2 } ; /* where yr ∈ path(yr , y2 )
*/
if (x∗r , yr∗ ) = φ then (x∗r , yr∗ ) ← (x2 , y2 );

p∗R0 ← path(rc , x∗r ) ∪ (x∗r , yr∗ ) ∪ path yr∗ , root(τ ) ;
pR0 ← pτ 0 ∪ path(x0 , par(vl ));
p01 ← path(par(x0 ), yr∗ )\{yr∗ };
T ← T ∪ Subtrees hanging from path(vL , x∗r ) ;
end
if xτ 0 6= φ then
/* Connected to p1 through τ 0 */
0
0
pτ 0 ← (y , yτ 0 ) ∪ path(yτ 0 , xτ 0 ) ∪ (xτ 0 , x );
p∗τ 0 ← path(LCA(xτ 0 , yτ 0 ), root(τ 0 ));
Tτ 0 ← Subtrees hanging from path(xτ 0 , yτ 0 ) and path(LCA(xτ 0 , yτ 0 ), root(τ 0 )) ;
else pτ 0 ← (y 0 , x0 ); p∗τ 0 = φ; Tτ 0 = φ;
Add p∗R0 and pR0 to T ∗ ;
T ← T ∪ Tτ 0 ∪ Subtrees hanging from path(rc , root(τ ))\{T
(vL )} ;

Return Process-Comp {pc , p01 , p∗τ 0 }, T ∪ Tc \τ, p∗R0 ∪ pR0 ;
/* Goes to DisConn, DisInt or Path-Halving
*/
32

