# Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet
Efficient

Surender Baswana  Heinz Nixdorf Institute, University of Paderborn, Paderborn,
Germany (https://www.hni.uni-paderborn.de), email<EMAIL_ADDRESS>Shiv
Kumar Gupta  Dept of Computer Science & Engineering, Indian Institute of
Technology Kanpur, Kanpur, India (https://www.cse.iitk.ac.in), email:
<EMAIL_ADDRESS>Ayush Tulsyan 22footnotemark: 2

###### Abstract

We present an algorithm for a fault tolerant Depth First Search (DFS) Tree in
an undirected graph. This algorithm is drastically simpler than the current
state-of-the-art algorithms for this problem, uses optimal space and optimal
preprocessing time, and still achieves better time complexity. This algorithm
also leads to a better time complexity for maintaining a DFS tree in a fully
dynamic environment.

##  1 Introduction

Depth First Search (DFS) is a widely popular graph traversal method. The
traversal routine, formalized by Tarjan [41] in 1972, has played a crucial
role in various graph problems including reachability, bi-connectivity,
topological sorting, and strongly connected components.

Given an undirected graph $G=\left({V,E}\right)$ with $n=|V|$ vertices and
$m=|E|$ edges, DFS traversal on the graph takes
${\mathcal{O}}\left({{m+n}}\right)$ time and results in a DFS tree (a rooted
spanning tree) of $G$. The traversal also classifies all the edges into tree
edges and back edges.

Almost all real-world problems on graphs deal with updates. Vertices and edges
keep entering and leaving the graph all the time. This update sensitive nature
of graphs has motivated researchers to find methods for updating the solutions
efficiently. There has been significant work in this area in the last two
decades.

The fault tolerant version of any problem $\mathcal{P}$ on a graph $G$ is to
construct a compact data structure, using which, for any set of failed edges
or vertices $F$, one can efficiently report the solution of $\mathcal{P}$ on
$G\setminus F$. Many elegant fault tolerant algorithms have been designed for
problems including connectivity [12, 20, 23], shortest paths [7, 15, 19], and
spanners [10, 14].

The dynamic version of any problem $\mathcal{P}$ on $G$ is modeled as follows.
For any online sequence of updates (insertion or deletion of edges/vertices),
one has to report the solution of $\mathcal{P}$ efficiently after every
update. Note that, unlike the fault tolerant version, the updates are
persistent in dynamic version, i.e., after each update, the solution has to be
reported taking into account all the updates made so far. Algorithms which
handle both insertion and deletion of vertices/edges are called fully dynamic
graph algorithms, whereas the algorithms that handle either insertions or
deletions are called partially dynamic graph algorithms, more specifically
incremental or decremental graph algorithms, respectively. The prominent
results for dynamic graph problems include connectivity [21, 26, 27, 28],
reachability [36, 38], shortest path [18, 37], matching [5, 9, 40], spanner
[8, 24, 35], and min cut [42].

###  1.1 Previous Results on Fault Tolerant and Dynamic DFS

Apart from the hardness results for the dynamic oredred DFS problem (Reif [33,
34], Miltersen _et al_. [29]), little contribution was made until recently.
For directed acyclic graphs (DAG), Franciosa  _et al_. [22] presented an
algorithm for maintaining a DFS tree under incremental edge updates which
takes overall ${\mathcal{O}}\left({{mn}}\right)$ time for any sequence of $m$
edge insertions. For undirected graphs, Baswana and Khan [6] in 2014 presented
an incremental algorithm for a DFS tree which takes overall
${\mathcal{O}}\left({{n^{2}}}\right)$ time for any sequence of edge
insertions. Baswana and Choudhary [3] designed a randomized decremental
algorithm for a DFS tree in DAGs with overall expected
${\mathcal{O}}\left({{mn\log{n}}}\right)$ time over any sequence of edge
deletions.

None of the partially dynamic algorithms stated above achieves an
$o\left({m}\right)$ bound over the worst-case complexity of a single update.
Moreover, there were no fully dynamic or fault tolerant algorithms for DFS in
undirected graphs until recently. In 2016, the first fault tolerant algorithm
was presented that takes $O(nk\log^{4}n)$ time to report a DFS tree for any
set of $k$ failed vertices or edges [2]. The time complexity was further
improved by Chen _et al_. [16] to ${\mathcal{O}}\left({{nk\log^{2}n}}\right)$.
Both [2, 16] require a data structure occupying
${\mathcal{O}}\left({{m\log^{2}{n}}}\right)$ bits. Nakamura and Sadakane [31]
reduced the space occupied by the data structure to
${\mathcal{O}}\left({{m\log{n}}}\right)$ bits which is indeed optimal
111Precisely, their data structure occupies
$\left({m+o\left({m}\right)}\right)\log{n}$ bits by using a wavelet tree.. The
fault tolerant algorithms presented in [2, 16, 31] lead to $o\left({m}\right)$
fully dynamic algorithms for maintaining a DFS tree using the standard
technique of periodic rebuilding (refer to Table 1). Recently, Chen _et al_.
[17] designed an ${\mathcal{O}}\left({{n}}\right)$ time incremental algorithm
for DFS tree in undirected graphs, which is optimal if it is required to
output the DFS tree after each update.

###  1.2 Familiarizing with the Problem

For an undirected graph, the depth first nature of the traversal ensures that
there are no cross edges in the resulting DFS tree. Following lemma states
this property (referred to as DFS Property henceforth):

######  Lemma 1.

For each vertex $v\in V$, a neighbour of $v$ appears either as an ancestor of
$v$ or as a descendant of $v$ in any DFS tree.

We now define the ancestor-descendant path.

######  Definition 2.

(Ancestor-descendant path) A path in a DFS tree is called an ancestor-
descendant path if its endpoints have an ancestor-descendant relationship in
the tree.

In the presence of failures of vertices or edges, the aim is to update the
tree efficiently such that the DFS property is restored. In order to
familiarize the reader with the problem, let us consider another related, but
simpler problem, namely, rerooting of a DFS tree defined as follows.

######  Problem 3.

Preprocess an undirected graph $G=(V,E)$ to build a compact data structure so
that given any vertex $v\in V$, we can report the DFS tree rooted at $v$
efficiently.

$r$$s$$t$$u$$v$$w$$p$$x$$y$$z$ (a) a DFS tree rooted at $r$.

$v$$u$$t$$s$$r$$w$$p$$x$$y$$z$ (b) reversing $path(r,v)$ results into cross
edges.

Figure 1: Non-triviality of rerooting problem.

Let $T$ be an initial DFS tree, rooted at a vertex, say $r$. For computing a
DFS tree rooted at any vertex $v$, the most obvious solution may be to just
reverse the direction of the path from $r$ to $v$ in $T$. However, this may
result in transforming many back edges to cross edges and hence a violation of
the DFS property (see Figure 1). To fix this problem, we may need to reroot
various subtrees hanging from the reversed path. Along these lines, [2]
presented an algorithm that takes $O(n\log^{3}n)$ time to compute a DFS tree
rooted at any vertex.

In order to see how rerooting a DFS tree is related to the problem of fault
tolerant DFS tree, consider the failure of vertex $u$ in Figure 1(a). The
subtree $T(v)$ is connected to the remaining tree through many back edges and
$(p,t)$ is the lowest among all of them. If we reroot the subtree $T(v)$ at
vertex $p$ and hang it from the remaining tree through the edge $(p,t)$, this
provides a valid DFS tree of $G\backslash\\{u\\}$.

The problem of fault tolerant DFS tree becomes more complex in the presence of
multiple faults. However, the distribution of faults plays an important role
as follows. If the failing vertices do not have any ancestor-descendant
relationship in the DFS tree, they can be handled independently. For example,
the simultaneous failure of vertices $u$ and $x$ in the DFS tree shown in
Figure 1(a) requires rerooting the respective subtrees $T(v)$ and $T(y)$ at
vertices $p$ and $z$ respectively. So, even for arbitrarily large number of
failures, if none of them have the ancestor-descendant relationship, we have
to just reroot the corresponding disjoint subtrees of $T$ to report the DFS
tree avoiding those failures. If two or more failures indeed have the
ancestor-descendant relationship, [2] presents an algorithm which is quite
different from their rerooting algorithm.

###  1.3 Overview of the Previous Results

We now begin with an overview of the existing algorithms for fault tolerant
DFS tree. For any set of $k$ failures, the algorithm presented in [2] first
partitions the original DFS tree into a pool of connected components. This
pool consists of $k$ paths (specifically, ancestor-descendant paths) and
potentially a large number of subtrees. The algorithm treats each of these
components as a super vertex and uses them to grow the DFS tree $T^{*}$ that
avoids all the failures. At a high level, the algorithm can be visualized as a
traversal on these super vertices. Each traversal extracts a path from the
super vertex, attaches it to $T^{*}$, and places the remaining portion of the
super vertex back into the pool. In order to pursue DFS traversal further in
an efficient manner, the algorithm needs to compute minimal adjacency lists
for the vertices of the traversed path (referred to as reduced adjacency
lists). The algorithm makes use of the following crucial property of DFS
traversal.

######  Lemma 4.

[Components Property [2]] Consider any DFS Traversal on any undirected graph
$G=\left({V,E}\right)$. When the traversal reaches a vertex $v\in V$, let the
set of connected components induced by the unvisited vertices be $C$. If from
any component $c\in C$, there exists two edges - $e$ to vertex $v$ and
$e^{\prime}$ to any of the visited vertices (including $v$), then for building
a valid DFS tree, it is sufficient to consider only the edge $e$ during the
rest of DFS traversal, that is, $e^{\prime}$ can be ignored.

In order to use the above property to populate the reduced adjacency list, the
algorithm needs a data structure to answer the following queries repeatedly.

  * •

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

  * •

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

It is quite obvious from the description given above that these queries are
quite non-trivial, and so a sophisticated data structure is designed in [2] to
answer these queries efficiently. In addition to the complex data structure,
the complete difference in the processing of a path and a subtree obfuscates
the algorithm and its analysis.

The subsequent results [16, 31] keep the algorithm unchanged and replace the
data structure used in [2] with alternate data structures. Chen _et al_. [16]
model the two queries mentioned above as Orthogonal Range
Successor/Predecessor(ORS/ORP) queries and this improves the query processing
time. Nakamura and Sadakane [31] compressed the data structure used in [16]
using Wavelet Trees [25] to achieve optimal space. Despite these improvements,
the core of the fault tolerant algorithm remains intricate and the data
structure still remains complex. Recently, in an empirical study [4], it was
found that this algorithm performs even worse than the static DFS algorithm
for certain classes of graphs. This naturally raises the question if there
exists a simpler algorithm for this fundamental problem.

Moreover, all these algorithms fail to incorporate the distribution of the
faults to achieve efficiency - Consider the case where very few among the $k$
faults in the tree have an ancestor-descendant relationship, these algorithms
process this input in a way similar to the input with worst case distribution
of the faults and take $O(nk\text{ }polylog(n))$ time although there is a
simple $O(n\text{ }polylog(n))$ time algorithm for such cases as described in
1.2.

###  1.4 Our Contribution

We take a much simpler approach as compared to the previous algorithms. We
decompose the DFS tree $T$ into a disjoint collection ${\cal P}$ of ancestor-
descendant paths. Similar to [2], each of these paths are treated like super
vertices. At a high level, the algorithm can still be viewed as a traversal on
these super vertices. However, as the reader may also verify, the algorithm
turns out to be lighter and quite different at the core. Interestingly, the
original DFS tree alone acts as a powerful data structure to be used for
rerooting or for the computation of another valid DFS tree in the presence of
faults. The algorithm crucially exploits an implicit hierarchy among the
ancestor-descendant paths in ${\cal P}$. This hierarchy along with the DFS
property of $T$ enables us to use much simpler queries. In particular, each
query will ask only for an edge from a vertex to one of its ancestor paths in
the hierarchy. The hierarchy allows us to represent $T$ as another tree like
structure, called shallow tree. In a nutshell, our algorithm can be viewed as
an efficient DFS traversal guided by this shallow tree.

We first present a new and simple rerooting algorithm based on the above
ideas. This rerooting algorithm extends to the fault tolerant algorithm with
very little and obvious modifications. While preserving simplicity, the fault
tolerant algorithm turns out to be faster than all the previous algorithms.
Moreover, our algorithm is the first to implicitly incorporate the
distribution of faults to gain efficiency. We summarize our result in the
following theorem.

######  Theorem 5.

An undirected graph $G$ and its DFS tree $T$ can be preprocessed in
${\mathcal{O}}\left({{m+n}}\right)$ time to build a data structure of
${\mathcal{O}}\left({{m+n}}\right)$ size, using which one can compute the DFS
tree of the graph for any given $k$ failed vertices or edges, in
${\mathcal{O}}\left({{n\left({k^{\prime}+\log{n}}\right)\log{n}}}\right)$
time, where $k^{\prime}\leq k$ is the maximum number of faults on any root-
leaf path in the tree $T$.

We now present the highlights of our algorithm.

Drastically simpler algorithm: Our algorithm is drastically simpler and more
intuitive than the previous algorithm. We feel confident to defend that it can
be taught even in an undergraduate course on algorithms. The pseudo-codes in
Algorithm 1 and Algorithm 2 are concise and very close to the corresponding
implementations.

Faster time complexity: Our algorithm takes $O(n(k^{\prime}\log n+\log^{2}n))$
time, where $k^{\prime}$ is the maximum number of failures on any ancestor-
descendant path of the DFS tree when $k$ edges/vertices fail. In the worst-
case $k^{\prime}$ can be as large as $k$. However, $k^{\prime}$ can be $o(k)$
as well. In the latter case, our result improves all the existing results
significantly. Moreover, even in the case $k^{\prime}=k$, our time complexity
is superior to the previous best by a $\log$ factor.

Optimal preprocessing time: Our preprocessing relies upon DFS traversal only,
taking ${\mathcal{O}}\left({{m+n}}\right)$ time. Given a graph, in order to
report the initial DFS tree, one anyway has to run a static DFS. Hence, our
preprocessing time is optimal.

Optimal space and elementary data structure: In contrast to the heavy data
structure used by [2, 16], our algorithm makes use of very elementary data
structures which are compact as well. Each vertex keeps array storing edges
incident on it from ancestors sorted according to their levels. This data
structure uses just $m$ words and still achieves
$O(n(k^{\prime}\log^{2}n+\log^{3}n))$ time to report a DFS tree upon failure
of any $k$ vertices or edges. By using fractional cascading [13], we get rid
of one $\log$ factor while still keeping space requirement to be $O(m)$.

Faster Fully Dynamic Algorithm: Using Theorem 5 and periodic rebuilding
technique used in [2], we also get the fastest (till date) algorithm for fully
dynamic DFS:

######  Theorem 6.

Given an undirected graph, one can maintain a DFS tree for any online sequence
of insertions and deletions of vertices/edges in
${\mathcal{O}}\left({{\sqrt{mn\log{n}}}}\right)$ worst-case time per update.

The new fully dynamic algorithm can be used to solve the dynamic subgraph
problems discussed in [2] and improves upon their time complexity as well (see
Appendix).

Table 1 offers a comparison of our results with all the previous results.

Table 1: Comparison of the existing results and the new algorithm | [2] | [16] | [31] | New
---|---|---|---|---
Space bits | $\mathcal{O}(m\log^{2}{n})$ | $\mathcal{O}(m\log^{2}{n})$ | $\mathcal{O}(m\log{n})$ | $\mathcal{O}(m\log{n})$
Preprocessing | $\mathcal{O}(m\log{n})$ | $\mathcal{O}(m\log{n})$ | ${\mathcal{O}}\left({{m\sqrt{\log{n}}}}\right)$ | ${\mathcal{O}}\left({{m+n}}\right)$
$k$-fault tolerant | $\mathcal{O}(nk\log^{4}{n})$ | $\mathcal{O}(nk\log^{2}{n})$ | $\mathcal{O}(nk\frac{\log^{3}{n}}{\log{\log{n}}})$ | ${\mathcal{O}}\left({{n(k^{\prime}+\log{n})\log{n}}}\right)$
Dynamic DFS | $\mathcal{O}(\sqrt{mn}\log^{2.5}n)$ | $\mathcal{O}(\sqrt{mn}\log^{1.5}{n})$ | $\mathcal{O}(\sqrt{mn}\frac{\log^{1.75}{n}}{\sqrt{\log{\log{n}}}})$ | $\mathcal{O}(\sqrt{mn\log{n}})$

###  1.5 Organisation of the Paper

We now briefly present how this paper is organized. Section 2 introduces the
notations and some well-known techniques/properties used throughout the paper.
Section 3 first defines the shallow tree representation, a concise structure
which encapsulates the hierarchy of paths in the initial DFS tree. Section 4
is the core of our work. Here, we describe how a DFS tree can be rerooted
efficiently. Section 5 describes how with some minor modifications to the data
structure, rerooting procedure extends to a fault tolerant algorithm. We
present the fully dynamic algorithm and its application to various dynamic
subgraph problems in Section 6.

##  2 Preliminaries

###  2.1 Notations

Following notations will be used throughout this paper.

  * •

$T$: Any DFS tree of the original graph $G$.

  * •

$path\left({x,y}\right)$: the path from vertex $x$ to $y$ in $T$.

  * •

$dfn\left({x}\right)$: The depth first number, i.e., the number at which
vertex $x$ is visited during the DFS traversal.

  * •

$v\left({i}\right)$: the vertex $x\in V$ such that $dfn(x)=i$.

  * •

$T\left({x}\right)$: the subtree of $T$ rooted at vertex $x$.

For the sake of ease of explanation, we shall assume that the graph remains
connected at all times. This assumption is without loss of generality because
of the following standard way of transforming the original graph right in the
beginning - Introduce a dummy vertex $r$ and connect it to all vertices of the
graph. Henceforth, we maintain a DFS tree rooted at $r$ for this augmented
graph. It is easy to observe that the augmented graph remains connected
throughout and the DFS tree rooted at $r$ will be such that the subtrees
rooted at the children of $r$ constitute the DFS forest of the original graph.

###  2.2 Heavy-Light Decomposition

Sleator and Tarjan, in their seminal result on dynamic trees [39] introduced a
technique of partitioning any rooted tree called Heavy-light decomposition.
Given any rooted tree, this technique splits it into a set of vertex-disjoint
ancestor-descendant paths. It marks all the tree edges either dashed or solid
- a tree edge is marked solid iff the subtree of the child vertex is heaviest
among the subtrees of all its siblings and dashed otherwise. A maximal
sequence of vertices connected through solid edges constitutes the required
ancestor-descendant path. This decomposition can be carried out easily in
${\mathcal{O}}\left({{n}}\right)$ time.

###  2.3 Fractional Cascading

Given $n$ sorted arrays and a value $x$, suppose we need to find the
predecessor/successor of $x$ in each of them. A naive way is to make a binary
search on each array. Chazelle and Guibas [13] introduced a novel tool called
fractional cascading using which this problem can be solved more efficiently.
Also, Chen _et al_.[17] used this tool for arriving at an
${\mathcal{O}}\left({{n}}\right)$ algorithm for incremental updates. We adapt
a customized version of their method.

######  Lemma 7.

Fractional cascading: Given $n$ sorted arrays $\\{A_{i}\\}_{i\in[n]}$ each
with size $l_{i}=|A_{i}|$ and cumulative size, $\sum_{i}^{n}l_{i}=m$, there
exists an ${\mathcal{O}}\left({{m}}\right)$ space data structure which can be
built in ${\mathcal{O}}\left({{m}}\right)$ time, such that for any given
$x,i,$ and $k$ satisfying $i,k\in[n]$ and $i+k\leq n$, we can search for $x$
(or its predecessor/successor) in all arrays $A_{i},\dots,A_{i+k}$ using the
data structure in $O(k+\log{m})$ time.

For the sake of completeness, we provide a description about the structure in
Lemma 7.

Build $n$ sorted arrays $\\{\mathcal{F}_{i}\\}_{i\in[n]}$ as follows.
$\mathcal{F}_{1}$ is a copy of $A_{1}$. For $i>1$, $\mathcal{F}_{i}$ will be
built by merging $A_{i}$ and $\mathcal{F}_{i-1}^{even}$. Here,
$\mathcal{F}_{t}^{even}$ represents the array consisting of the elements at
even indices in $\mathcal{F}_{t}$, i.e.,
$\mathcal{F}_{t}^{even}[j]=\mathcal{F}_{t}[2j]\hskip 8.61108pt\forall
j\in[\lfloor n/2\rfloor]$. Note that all $\mathcal{F}_{i}$’s remain sorted
after the merge. The number of elements in this structure is at most $2m$.

For each element $v$ in any array $\mathcal{F}_{i}$, we store two pointers,
one to $A_{i}$ and one to $\mathcal{F}_{i-1}^{even}$. They point to the
elements in the corresponding array that is just larger than or equal to $v$.

To answer the query for any triplet of integers $x$, $i$, and $k$, first
search for $x$ in $\mathcal{F}_{i+k}$. Pointer to $A$ can be used to find the
required element in $A_{i+k}$. Now instead of making another binary search in
$\mathcal{F}_{i+k-1}$, pointer to $\mathcal{F}_{i+k-1}^{even}$ stored at the
element in $\mathcal{F}_{i+k}$ is utilized. This leads us to the required
element (or its immediate neighbours) in $\mathcal{F}_{i+k-1}$. By comparing
$x$ with the element at pointed location (and its immediate neighbours), one
can reach where another binary search would have led us. Here, again pointers
to $A_{i+k-1}$ and $\mathcal{F}_{i+k-2}^{even}$ are available. This process
can be repeated till one reaches $\mathcal{F}_{i}$.

##  3 Shallow Tree Representation

We now introduce the shallow tree representation for DFS tree $T$ that plays a
key role in our algorithm. Using heavy-light decomposition, $T$ is broken down
into a set of vertex-disjoint ancestor-descendant paths. Let’s denote this set
with $\mathcal{P}$. Observe that these paths are connected through dashed
edges in $T$. These edges introduce a hierarchy among paths in $\mathcal{P}$
and the shallow tree defined below captures this hierarchy.

######  Definition 8.

Given a DFS tree $T$ of an undirected graph $G$, let $\mathcal{P}$ be the set
of paths obtained through heavy-light decomposition of $T$. Let $H$ be the set
of edges marked dashed during the decomposition. For tree $T$, its shallow
tree $S$ is a rooted tree formed by collapsing each element of ${\cal P}$ into
a single node (super vertex). Note that, for each edge $(y,z)\in H$ with
$y=parent(z)$, the node in $S$ that contains $y$ is the parent of the node
containing $z$.

$a$$b$$c$$d$$e$$f$$g$$h$$i$$j$$k$$l$ (a)

$a$$b$$c$$d$$e$$f$$g$$h$$i$$j$$k$$l$$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$$p_{6}$
(b)

$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$$p_{6}$ (c)

Figure 2: DFS Tree $T$, Heavy Light decomposition with paths in $\mathcal{P}$,
and the corresponding Shallow Tree.

Figure 2 demonstrates how a DFS tree is decomposed to form a set of ancestor-
descendant paths $\mathcal{P}$ which is subsequently used to form the shallow
tree $S$.

To avoid ambiguity, we address the vertices in the shallow tree as ‘nodes’ and
the vertices in the DFS tree as ‘vertices’. $node\left({x}\right)$ denotes the
shallow tree node corresponding to the path in ${\cal P}$ containing vertex
$x$.

The construction of $S$ described above ensures the following simple but
crucial properties.

  * •

As a result of heavy-light decomposition of a tree $T$ with $n$ vertices,
there can be at most $\log{n}$ dashed edges on any root to leaf path in $T$.
Recall that each edge in $S$ corresponds to a dashed edge. Thus, the depth of
any node in tree $S$ can’t be larger than $\log{n}$. It is because of this
small depth that we choose the name shallow tree for $S$.

  * •

From the DFS property, neighbours of any vertex $v\in V$ are either ancestors
or descendants of $v$ in $T$. Consider any such neighbour $u$. Let $p_{1}$ be
the path in $\mathcal{P}$ containing $v$ and $p_{2}$ be the path in ${\cal P}$
containing $u$. $u$ and $v$ may also lie in the same path in $\mathcal{P}$.
From the construction of $S$, $p_{1}$ and $p_{2}$ will share an ancestor-
descendant relation in $S$. So we can state the following lemma.

######  Lemma 9.

For a DFS tree $T$ of an undirected graph $G=\left({V,E}\right)$ with shallow
tree $S$, any vertex $v\in V$ which lies in node $\mu\in S$ can have edges
only to vertices lying in the nodes which are ancestors or descendants of
$\mu$ in $S$.

We require that the vertices of each solid path have consecutive $dfn$. This
enables us to represent each path $p\in\mathcal{P}$ in a compact manner using
just the smallest and largest $dfn$ of vertices on $p$. For each path $p$, we
store this pair as $PathEndPoints$ at the corresponding node of the shallow
tree $S$. Assigning consecutive $dfn$ to each solid path can be accomplished
easily - we carry out another DFS on $T$ where for each vertex, the next
vertex to be visited is its child hanging through a solid edge (Refer to
Algorithm 4 in Appendix).

##  4 Rerooting DFS Tree $T$

Given a DFS tree $T$ for a graph $G=\left({V,E}\right)$ and a vertex
$r^{\prime}\in V$, the objective is to compute a DFS tree $T^{*}$ rooted at
$r^{\prime}$ for the same graph $G$. First we compute the shallow tree
representation $S$ of $T$ in ${\mathcal{O}}\left({{n}}\right)$ time. We now
describe the rerooting procedure.

###  4.1 Reroot Procedure

The tree $T^{*}$ is empty in the beginning and is grown gradually starting
from $r^{\prime}$. To build this tree efficiently, the idea is to re-use the
paths from ${\cal P}$. In addition, we aim to populate a reduced adjacency
list for each vertex, which should be small and yet sufficient to compute a
DFS tree.

The intuition sketched above is materialized by carrying out a DFS traversal
guided by the shallow tree $S$. Note that a node of the shallow tree
corresponds to a path in ${\cal P}$. To compute $T^{*}$, our algorithm
performs a sequence of steps. Each step begins with entering a node of $S$
through some vertex present on the path stored at the node and leaving it
after traversing the path along one direction. The first node to be visited is
$node(r^{\prime})$. We now provide complete details of the computation
involved in each step. Consider any node $\nu\in S$. Let $path(y,z)$ be the
path corresponding to $\nu$. When the DFS traversal enters $\nu$ through a
vertex, say $x$, the following 3 simple operations are carried out.

  1. 1.

_Move towards the farther end of the path._
We determine the vertex from $\\{y,z\\}$ farther from $x$. Let this vertex be
$y$. DFS traversal proceeds from $x$ to $y$ and $path(x,y)$ is attached to the
tree $T^{*}$. Next, we update the $PathEndpoints\left({\nu}\right)$ such that
it stores the endpoints of the untraversed part of $path(y,z)$.

  2. 2.

_Populate the reduced adjacency list of the path just traversed._
For vertices on $path(x,y)$, we populate the reduced adjacency list
$\mathcal{L}$ using ancestors and descendants of $\nu$ in the shallow tree
$S$. This has been explained below in Section 4.1.1.

  3. 3.

_Continue traversal._
Using the reduced adjacency list $\mathcal{L}$ of the traversed path computed
in step 2 above, we continue the DFS traversal along the unvisited neighbours
of the vertices in the order from $y$ to $x$ (opposite to the direction of
traversal, due to the recursive nature of DFS).

Algorithm 1 presents the complete pseudocode of the rerooting procedure based
on the above 3 steps. Invoking Reroot$(r^{\prime})$ produces the DFS tree
rerooted at $r^{\prime}$.

1Function  _Reroot (x)_

2 $(y,z)\leftarrow PathEndpoints\left({node\left({x}\right)}\right)$ ;

3 if  _ $dist(x,z)>dist(x,y)$ _ then $\text{Swap}\left({y,z}\right)$;

4 /* compute $dist$ using $dfn$s */ Attach $path\left({x,y}\right)$ to
$T^{*}$;

5 if  _$x\neq z$_ then

6 $w\leftarrow\text{Neighbour of }x\text{ on }path(y,z)\text{ nearest to }z$ ;

$PathEndpoints\left({node\left({x}\right)}\right)\leftarrow\left({w,z}\right)$
;

/* untraversed path */

7

8 end if

9

10 $\mathcal{L}\leftarrow
ReducedAL\left({\mathcal{L},\left({x,y}\right)}\right)$ ;

11 for  _$i=\text{dfn}(y)$ to $\text{dfn}(x)$_ do $status(v(i))\leftarrow
visited$ ;

12 for  _$i=\text{dfn}(y)$ to $\text{dfn}(x)$_ do

13 foreach  _vertex $u\in\mathcal{L}(v(i))$_ do

14 if  _ $status(u)=unvisited$ _ then {add
$\left({v\left({i}\right),u}\right)$ to $T^{*}$; Reroot($u$)} ;

15

16 end foreach

17

18 end for

19

20

Algorithm 1 Recursive procedure to reroot the DFS Tree $T$

####  4.1.1 Populating Reduced Adjacency Lists

Here we define a query $Q\left({u,(p_{s},p_{e})}\right)$, where
$u,p_{s},p_{e}\in V$ satisfy the following constraints:

  * •

$p_{s}$ and $p_{e}$ are the end-points of an ancestor-descendant path in $T$.

  * •

$u$ is a descendant of the highest vertex on the
$path\left({p_{s},p_{e}}\right)$, but does not lie on the path.

This query returns the edge from vertex $u$ that is incident to the
$path(p_{s},p_{e})$ closest to $p_{e}$, but returns null if no such edge
exists.

Consider any node $\nu\in S$, and let $path(y,z)$ be its corresponding path in
${\cal P}$. When the DFS traversal enters $\nu$ through $x$ and proceeds
towards $y$, we populate the reduced adjacency lists of vertices on
$path(x,y)$ using Lemma 9 as follows.

  * •

Processing Ancestors.
For each $u\in path(x,y)$ and for each ancestor $\mu$ of $\nu$, we add
$Q\left({u,PathEndpoints\left({\mu}\right)}\right)$ to
$\mathcal{L}\left({u}\right)$.

  * •

Processing Descendants.
Using the shallow tree $S$, one can list all the vertices that are descendants
of $path(x,y)$ in $T$. From all these vertices, we query for an edge to
$path(x,y)$ which is incident closest to $y$. For any descendant $u$, if the
query $Q\left({u,\left({x,y}\right)}\right)$ returns a non-null value, say
$w$, then we add $u$ to $\mathcal{L}\left({w}\right)$.

######  Remark 1.

In Algorithm 1, after visiting $x$, if we moved towards the leaf node, then
the untraversed part of $\nu$ has to be treated as an ancestor path while
populating the reduced adjacency lists of $path\left({x,y}\right)$, and as a
descendant path, otherwise.

1Function  _ReducedAL $\left({\mathcal{L},\left({x,y}\right)}\right)$_

2 $\mu\leftarrow\text{parent}\left({\text{node}\left({x}\right)}\right)$;

3 while  _$\mu\neq\text{NULL}$_ do /* edges to ancestor paths */

4 for  _$i=\text{dfn}(y)$ to $\text{dfn}(x)$_ do

5
$\mathcal{L}\left({v\left({i}\right)}\right)\leftarrow\mathcal{L}\left({v\left({i}\right)}\right)\cup
Q(v\left({i}\right),PathEndPoints\left({\mu}\right))$;

6

7 end for

8 $\mu\leftarrow parent(\mu)$ ;

9

10 end while

11 if  _$\text{dfn}\left({x}\right) <\text{dfn}\left({y}\right)$_ then
$z\leftarrow x$ else $z\leftarrow y$;

12 /* $z$ is ancestor among two */
$\mathcal{C}\leftarrow\text{Desc}_{T}\left({z}\right)\setminus\left\\{{v\left({dfn\left({x}\right)}\right),\dots,v\left({dfn\left({y}\right)}\right)}\right\\}$;

13 foreach  _$u\in\mathcal{C}$_ do /* each descendant of
$path\left({x,y}\right)$ */

$w\leftarrow Q\left({u,\left({x,y}\right)}\right)$ ;

/* ensure $w$ is closest to $y$ */

14 if  _$w\neq\text{NULL}$_ then
$\mathcal{L}\left({w}\right)\leftarrow\mathcal{L}\left({w}\right)\cup\\{u\\}$
;

15

16 end foreach

17 return $\mathcal{L}$

18

Algorithm 2 Populating reduced adjacency lists of vertices on $path(x,y)$.

In Algorithm 2, we used query $Q\left({u,\left({p_{s},p_{e}}\right)}\right)$
as a black box. This query can be answered very easily as follows. The
constraints of $Q\left({u,\left({p_{s},p_{e}}\right)}\right)$ imply that the
returned edge is always an edge from $u$ to an ancestor of $u$. For answering
this query, we use a data structure $\mathcal{D}$ which stores the following
information for each vertex $u$.

######  Definition 10.

$\mathcal{D}\left({u}\right)$ is an array that stores all the ancestors of $u$
in $T$ to which $u$ is a neighbour and it stores them in the increasing order
of distance from the root.

This data structure enables us to answer query
$Q\left({u,\left({p_{s},p_{e}}\right)}\right)$ using a binary search on array
$\mathcal{D}\left({u}\right)$ and it takes
${\mathcal{O}}\left({{\log{n}}}\right)$ time only. Interestingly, the data
structure $\mathcal{D}$ can be preprocessed very easily in $O(m+n)$ time as
follows. We visit vertices in the increasing order of their depth first
numbers. Note that for each vertex $v$, the neighbours of $v$ which have $dfn$
larger than that of $v$ are its descendants. For each such descendant $u$, we
append $v$ to $\mathcal{D}(u)$. Iterating in increasing order of $dfn$ ensures
that all arrays in $\mathcal{D}$ are sorted as needed (Refer to Algorithm 3 in
Appendix).

######  Theorem 11.

Given a DFS Tree $T$ of an undirected graph $G$, there exists a data structure
which occupies exactly $m$ words, can be constructed in
${\mathcal{O}}\left({{m+n}}\right)$ time and can answer the query
$Q\left({u,\left({p_{s},p_{e}}\right)}\right)$ in
${\mathcal{O}}\left({{\log{n}}}\right)$ time.

###  4.2 Time Complexity Analysis

During preprocessing, we need to build the DFS Tree $T$, carry out heavy-light
decomposition to obtain $P$, construct the shallow tree $S$, and build
$\mathcal{D}$. This processing as shown earlier can be completed in
${\mathcal{O}}\left({{m+n}}\right)$ time. The time complexity of the Reroot
procedure is bounded by the time required to populate the reduced adjacency
lists $\mathcal{L}$. This in turn, is bounded by the number of calls to query
$Q$.

To analyse the number of calls made from any vertex $w$, let $\nu$ be the node
in the shallow tree $S$, containing $w$. In general, if the bound on height of
$S$ is $d$, ReducedAL makes worst-case $d$ queries from $w$ to ancestors of
$\nu$. Also when an ancestor of $\nu$ in $S$, say $\mu$, is visited during
Reroot procedure, ReducedAL makes a query from $w$ to $\mu$. Note that when we
enter any path in $\mathcal{P}$, our choice of direction ensures that at least
half of the path is traversed. This path halving technique (also used in [1,
2]) ensures that any node in $S$ (or a path in P) is visited at most $\log{n}$
times. This implies that any such ancestor $\mu$ may be visited at most
$\log{n}$ times. Thus, we can have worst-case $d\left({\log{n}+1}\right)$
queries from $w$ to its ancestor paths throughout the Reroot procedure.
Summing over all the vertices, there can be at most
$nd\left({\log{n}+1}\right)$ calls to query $Q$. Therefore, populating the
reduced adjacency lists $\mathcal{L}$ takes overall
${\mathcal{O}}\left({{nd\log^{2}{n}}}\right)$ time. From section 3, we know
$d\leq\log{n}$. Thus, using theorem 11, we can state the following lemma.

######  Lemma 12.

Given a DFS Tree $T$ of an undirected graph $G$, there exists a data structure
of size ${\mathcal{O}}\left({{m+n}}\right)$ words, which can be constructed in
${\mathcal{O}}\left({{m+n}}\right)$ time, and it can be used to compute a DFS
Tree of $G$ rooted at any given vertex in
${\mathcal{O}}\left({{n\log^{3}{n}}}\right)$ time.

####  4.2.1 Getting rid of a $\log$ factor

Consider the moment when the Reroot procedure enters a
$path\left({y,z}\right)$ through the vertex $x$ and reaches the endpoint $y$.
In Algorithm 2, for each descendant $w$ of $path\left({x,y}\right)$, we
perform query $Q\left({w,\left({x,y}\right)}\right)$ separately. Instead,
using Fractional Cascading, we can perform all these queries together in an
efficient manner. Among $x$ and $y$, let $x$ be the vertex closer to the root
of $T$. As described earlier, all the vertices of $path(x,y)$ have consecutive
$dfn$, and so do the vertices of subtree $T\left({x}\right)$. Let
$last\left({x}\right)$ be the vertex in $T\left({x}\right)$ with the largest
$dfn$. Since vertices on $path\left({x,y}\right)$ have been visited, we need
to query for edges only from vertices with $dfn$ between
$dfn\left({y}\right)+1$ and $dfn\left({last\left({x}\right)}\right)$. Finding
edges to $path\left({x,y}\right)$ from these vertices can be done with a
single query to the fractionally cascaded $\mathcal{D}$ (Lemma 7). It takes
${\mathcal{O}}\left({{\log{m}+dfn\left({last\left({x}\right)}\right)-dfn\left({y}\right)}}\right)$
time to execute this query. We charge the $\log{m}$ part of the query time to
the vertices on $path\left({x,y}\right)$ and the
$dfn\left({last\left({x}\right)}\right)-dfn\left({y}\right)$ is distributed
among the descendant vertices. Thus, each descendant vertex incurs a constant
charge.

Note that, queries to the ancestors of $path\left({x,y}\right)$ are answered
using the original $\mathcal{D}$ itself. Therefore, in a shallow tree of
height $d$, each vertex $v\in V$ incurs following charges during Reroot
procedure - ${\mathcal{O}}\left({{d\log{n}}}\right)$ when $v$ acts as a
descendant in the queries made while visiting ancestors of $v$, and
${\mathcal{O}}\left({{d\log{n}+\log{m}}}\right)$ while visiting $v$ itself.
Overall the charge on any vertex is ${\mathcal{O}}\left({{d\log{n}}}\right)$
and, therefore, the time complexity of Reroot procedure reduces to
${\mathcal{O}}\left({{nd\log{n}}}\right)$. So we can state the following
lemma.

######  Lemma 13.

Given an undirected graph $G$ and a shallow tree with height $d$, there exists
a data structure which occupies ${\mathcal{O}}\left({{m+n}}\right)$ words, can
be constructed in ${\mathcal{O}}\left({{m+n}}\right)$ time, using which the
Reroot algorithm executes in ${\mathcal{O}}\left({{nd\log{n}}}\right)$ time.

###  4.3 Correctness of Reroot Procedure

As is evident from the pseudocode of Algorithm 1, besides populating the
reduced adjacency lists, Reroot can be seen as the usual DFS traversal. So in
order to show that Reroot indeed computes a valid DFS tree, all we need to
show is that the reduced adjacency list of each vertex is populated correctly.
We can show this as follows.

During Reroot procedure, consider the moment when we attach some path, say
$path(x,y)$ to $T^{*}$. Lemma 9 implies that all the neighbours of vertices on
the $path(x,y)$ will lie either in ancestors or in descendants of $path(x,y)$
in the shallow tree. For each descendant vertex of $path(x,y)$, we add an edge
incident on $path(x,y)$ closest to $y$ (lines 12,13 of Algorithm 2). For each
ancestor path of $path(x,y)$, we add an edge from each vertex of $path(x,y)$
(line 5 of Algorithm 2). This ensures that from each connected component in
the graph induced by unvisited vertices, the edge incident on $path(x,y)$
closest to vertex $y$ is surely added to $\mathcal{L}$ (if exists). Hence we
can conclude that Reroot procedure indeed computes a DFS tree.

##  5 Extension to Fault Tolerant DFS Tree

Let $F$ be the set of failures (edges/vertices) in any undirected graph $G$,
with $|F|=k$. Here, we describe how with some elementary modifications,
procedure Reroot can be utilized to report DFS tree of $G\setminus F$. First,
we update the set $\mathcal{P}$ and the shallow tree $S$ as follows.

  1. 1.

Each vertex maintains a state: active or failed. For a failed vertex $x\in V$,
we toggle $x$’s state to failed. Let $p\in{\cal P}$ be the path containing
$x$. We remove $x$ from $p$. The resulting smaller paths are added to
$\mathcal{P}$ and $p$ is removed from $\mathcal{P}$.

  2. 2.

For each failed edge $e=(u,v)$, we mark the corresponding entries in the
adjacency lists of $u$ and $v$ as failed. Here, we do not make any changes to
fractionally cascaded $\mathcal{D}$. If failed edge $e$ is a tree-edge and was
marked solid during heavy-light decomposition, $\mathcal{P}$ is updated as
follows. Path $p\in\mathcal{P}$ containing $e$ is split into two smaller
paths. These smaller paths are added to $\mathcal{P}$ and $p$ is removed from
$\mathcal{P}$.

  3. 3.

After updating $\mathcal{P}$, shallow tree $S$ is updated as per Definition 8.
For any path $p\in{\cal P}$, let the vertex in $p$ closest to root of $T$ be
$x$. The node in $S$ corresponding to $p$ is attached to $S$ as a child of the
node containing the closest active ancestor of $x$.

Given the set $F$, we can update $\mathcal{P}$ and $S$ in
${\mathcal{O}}\left({{n}}\right)$ time as follows - Make a DFS traversal
through $T$ while ensuring vertices are visited in increasing order of their
$dfn$. Update the paths and the edges in $S$ as discussed above. For each
failure, the number of nodes in $S$ increases by at most one. After $k$
updates, $S$ can have $k$ new nodes and may not be shallow anymore. Note that
the depth of a node $\nu$ in $S$ doesn’t increase due to any failure which
doesn’t lie on the path from $\nu$ to root of $S$. Thus, if the maximum of
number of failures on all root-leaf paths in $S$ is $k^{\prime}$, the height
of the shallow tree is at most $k^{\prime}+\log{n}$.

To ensure that no deleted vertices/edges are traversed during Reroot
procedure, we make the following modifications. The result of any query
$Q\left({v,\left({p_{s},p_{e}}\right)}\right)$ may be a failed edge or an edge
to a failed vertex. In such a case, we iterate in
$\mathcal{D}\left({v}\right)$ towards $p_{s}$ from the invalid edge until we
find an edge present in $G\setminus F$. However, if we cross $p_{s}$ in doing
so, we stop and return $null$. In the worst-case, we spend
${\mathcal{O}}\left({{nk^{\prime}+2k^{\prime}}}\right)$ time in such
iterations. Calling the procedure Reroot after above updates suffices to
report the DFS tree of $G\setminus F$. Using Lemma 13, we can conclude the
following theorem.

######  Theorem 14.

An undirected graph $G$ and its DFS tree $T$ can be preprocessed in
${\mathcal{O}}\left({{m+n}}\right)$ time to build a data structure of
${\mathcal{O}}\left({{m+n}}\right)$ size, using which one can compute the DFS
tree of the graph for any given $k$ failed vertices or edges, in
${\mathcal{O}}\left({{n\left({k^{\prime}+\log{n}}\right)\log{n}}}\right)$
time, where $k^{\prime}\leq k$ is the maximum number of faults on any root-
leaf path in the tree $T$.

##  6 Fully Dynamic DFS

We first describe how the fault tolerant DFS algorithm can handle incremental
updates. Following that, we use the overlapped periodic rebuilding technique
to arrive at a fully dynamic DFS algorithm. The ideas utilized in both of
these steps were used by Baswana _et al_. [2].

Let $U$ be the set of updates in any undirected graph $G$. In order to handle
each vertex insertion, we add the new vertices in $V$ and add the
corresponding edges to $E$ and $\mathcal{L}$. For the edges insertions, we
directly add these edges to reduced adjacency list of endpoints of the edge.
These modifications are sufficient to handle incremental updates. Since the
size of reduced adjacency lists after these updates is
${\mathcal{O}}\left({{n\left({|U|+\log{n}}\right)\log{n}}}\right)$, we get the
same worst-case time bound for the time complexity of Reroot procedure.

The following lemma helps us formulate the fully dynamic DFS algorithm from
the fault tolerant one.

######  Lemma 15.

(Lemma 6.1 in [2]) Let $\mathcal{D}$ be a data structure that can be used to
report the solution of a graph problem after a set of $U$ updates on an input
graph $G$. If $\mathcal{D}$ can be built in $O(f)$ time and the solution for
graph $G+U$ can be reported in $O(h+|U|\cdot g)$time, then $\mathcal{D}$ can
be used to report the solution after every update in worst-case
$O(\sqrt{fg}+h)$ update time, given that $f/g\leq n$.

Substituting $f=m$, $g=n\log{n}$ and $h=n\log^{2}{n}$, we obtain,
${\mathcal{O}}\left({{\sqrt{fg}+h}}\right)$ =
${\mathcal{O}}\left({{\sqrt{mn\log{n}}}}\right)$. Hence this implies the
following theorem:

######  Theorem 16.

An undirected graph can be preprocessed in ${\mathcal{O}}\left({{m+n}}\right)$
time to build a data structure occupying ${\mathcal{O}}\left({{m+n}}\right)$
words, using which one can maintain a DFS tree for any online sequence of
insertions and deletions of vertices/edges in
${\mathcal{O}}\left({{\sqrt{mn\log{n}}}}\right)$ worst-case time per update.

##  7 Conclusion

We presented a drastically simpler algorithm for DFS in an undirected graph in
fault tolerant setting. This algorithm takes $O(n(k^{\prime}+\log n)\log n)$
time for reporting a DFS tree for any given set of $k$ failed vertices/edges,
where $k^{\prime}$ is the maximum number of failed vertices/edges along any
root-leaf path of the initial DFS tree. This is superior to all the previous
bounds on this problem. Moreover, we achieve optimal space and optimal
preprocessing time.

Like each of the previous algorithms on this problem, our algorithm is
extendible to the case when we have insertion of vertices as well. For the
generic setting where $k$ updates may be insertion or deletion of vertices,
note that the input size of the query itself can take $\Theta(nk)$ space -
insertion of $k$ vertices each with $\Theta(n)$ edges. So our bounds may just
be nearly optimal for this generic setting. However, there may exist a faster
algorithm for the restricted case, especially when the updates are only
insertion or deletion of edges. It will be interesting to design faster
decremental and/or fully dynamic algorithm for DFS (when the updates are only
edges). We feel that the simplicity of the algorithm presented in this paper
will surely pave way for designing these algorithms.

## References

  * [1] 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.
  * [2] Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan.  Dynamic DFS in undirected graphs: breaking the O(_m_) barrier.  In Symposium on Discrete Algorithms, SODA, pages 730–739, 2016\.
  * [3] Surender Baswana and Keerti Choudhary.  On dynamic DFS tree in directed graphs.  In MFCS, Proceedings, Part II, pages 102–114, 2015.
  * [4] Surender Baswana, Ayush Goel, and Shahbaz Khan.  Incremental DFS algorithms: a theoretical and experimental study.  In Symposium on Discrete Algorithms, SODA, pages 53–72, 2018\.
  * [5] Surender Baswana, Manoj Gupta, and Sandeep Sen.  Fully dynamic maximal matching in O(log n) update time (corrected version).  SIAM J. Comput., 47(3):617–650, 2018.
  * [6] Surender Baswana and Shahbaz Khan.  Incremental algorithm for maintaining DFS tree for undirected graphs.  In ICALP, Proceedings, Part I, pages 138–149, 2014.
  * [7] Surender Baswana and Neelesh Khanna.  Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs.  Algorithmica, 66(1):18–50, 2013.
  * [8] Surender Baswana, Sumeet Khurana, and Soumojit Sarkar.  Fully dynamic randomized algorithms for graph spanners.  ACM Trans. Algorithms, 8(4):35:1–35:51, 2012.
  * [9] Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano.  Deterministic fully dynamic data structures for vertex cover and matching.  SIAM J. Comput., 47(3):859–887, 2018.
  * [10] Gilad Braunschvig, Shiri Chechik, David Peleg, and Adam Sealfon.  Fault tolerant additive and ($\mu$, $\alpha$)-spanners.  Theor. Comput. Sci., 580:94–100, 2015.
  * [11] Timothy M. Chan.  Dynamic subgraph connectivity with geometric applications.  SIAM J. Comput., 36(3):681–694, 2006.
  * [12] Timothy M. Chan, Mihai Patrascu, and Liam Roditty.  Dynamic connectivity: Connecting to networks and geometry.  In Symposium on Foundations of Computer Science, FOCS, pages 95–104, 2008.
  * [13] Bernard Chazelle and Leonidas J. Guibas.  Fractional cascading: I. A data structuring technique.  Algorithmica, 1(2):133–162, 1986.
  * [14] Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty.  Fault tolerant spanners for general graphs.  SIAM J. Comput., 39(7):3403–3423, 2010.
  * [15] Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty.  f-sensitivity distance oracles and routing schemes.  Algorithmica, 63(4):861–882, 2012.
  * [16] Lijie Chen, Ran Duan, Ruosong Wang, and Hanrui Zhang.  Improved algorithms for maintaining DFS tree in undirected graphs.  CoRR, abs/1607.04913, 2016.
  * [17] Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, and Tianyi Zhang.  An improved algorithm for incremental DFS tree in undirected graphs.  In SWAT, pages 16:1–16:12, 2018.
  * [18] Camil Demetrescu and Giuseppe F. Italiano.  A new approach to dynamic all pairs shortest paths.  J. ACM, 51(6):968–992, 2004.
  * [19] Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran.  Oracles for distances avoiding a failed node or link.  SIAM J. Comput., 37(5):1299–1318, 2008.
  * [20] Ran Duan.  New data structures for subgraph connectivity.  In ICALP, Proceedings, Part I, pages 201–212, 2010.
  * [21] David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig.  Sparsification - a technique for speeding up dynamic graph algorithms.  J. ACM, 44(5):669–696, 1997.
  * [22] 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.
  * [23] Daniele Frigioni and Giuseppe F. Italiano.  Dynamically switching vertices in planar graphs.  Algorithmica, 28(1):76–103, 2000.
  * [24] Lee-Ad Gottlieb and Liam Roditty.  Improved algorithms for fully dynamic geometric spanners and geometric routing.  In Symposium on Discrete Algorithms, SODA, pages 591–600, 2008\.
  * [25] Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter.  High-order entropy-compressed text indexes.  In Symposium on Discrete Algorithms, SODA, pages 841–850, 2003\.
  * [26] Monika Rauch Henzinger and Valerie King.  Randomized fully dynamic graph algorithms with polylogarithmic time per operation.  J. ACM, 46(4):502–516, 1999.
  * [27] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup.  Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.  J. ACM, 48(4):723–760, 2001.
  * [28] Bruce M. Kapron, Valerie King, and Ben Mountjoy.  Dynamic graph connectivity in polylogarithmic worst case time.  In Symposium on Discrete Algorithms, SODA, pages 1131–1142, 2013\.
  * [29] Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, and Roberto Tamassia.  Complexity models for incremental computation.  Theor. Comput. Sci., 130(1):203–236, 1994.
  * [30] Kengo Nakamura.  Fully dynamic connectivity oracles under general vertex updates.  In 28th International Symposium on Algorithms and Computation, ISAAC, pages 59:1–59:12, 2017.
  * [31] Kengo Nakamura and Kunihiko Sadakane.  A space-efficient algorithm for the dynamic DFS problem in undirected graphs.  In In International Workshop on Algorithms and Computation, pages 295–307, 2017.
  * [32] Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen.  Dynamic minimum spanning forest with subpolynomial worst-case update time.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 950–961, 2017.
  * [33] John H. Reif.  Depth-first search is inherently sequential.  Inf. Process. Lett., 20(5):229–234, 1985.
  * [34] John H. Reif.  A topological approach to dynamic graph connectivity.  Inf. Process. Lett., 25(1):65–70, 1987.
  * [35] Liam Roditty.  Fully dynamic geometric spanners.  Algorithmica, 62(3-4):1073–1087, 2012.
  * [36] Liam Roditty and Uri Zwick.  Improved dynamic reachability algorithms for directed graphs.  SIAM J. Comput., 37(5):1455–1471, 2008.
  * [37] Liam Roditty and Uri Zwick.  Dynamic approximate all-pairs shortest paths in undirected graphs.  SIAM J. Comput., 41(3):670–683, 2012.
  * [38] Piotr Sankowski.  Dynamic transitive closure via dynamic matrix inverse (extended abstract).  In Symposium on Foundations of Computer Science, FOCS, pages 509–517, 2004.
  * [39] Daniel Dominic Sleator and Robert Endre Tarjan.  A data structure for dynamic trees.  J. Comput. Syst. Sci., 26(3):362–391, 1983.
  * [40] Shay Solomon.  Fully dynamic maximal matching in constant update time.  In Symposium on Foundations of Computer Science, FOCS, pages 325–334, 2016.
  * [41] Robert Endre Tarjan.  Depth-first search and linear graph algorithms.  SIAM J. Comput., 1(2):146–160, 1972.
  * [42] Mikkel Thorup.  Fully-dynamic min-cut.  Combinatorica, 27(1):91–127, 2007.

##  Appendix A Applications of Fully Dynamic DFS

Baswana et al. [2] in the full version of their paper show how their algorithm
can be used to solve various dynamic subgraph problems such as dynamic
subgraph connectivity, biconnectivity, and 2-edge connectivity. In this
section, we state these problems and show how the new algorithm can be used to
improve the worst case time complexity.

###  A.1 Dynamic Subgraph Connectivity

#### Problem definition & Existing results

Given an undirected graph, the goal is to process an input stream of updates
and queries as efficiently as possible. Each update toggles the state of some
vertex in the graph from active to inactive or vice-versa. The queries check
if any given pair of vertices are connected in the subgraph induced by active
vertices. Chan [11] formally introduced this problem in 2006. They presented
an algorithm with ${\mathcal{O}}\left({{m^{0.94}}}\right)$ amortized update
time that could answer connectivity queries in $\tilde{\cal
O}\left({m^{1/3}}\right)$ time. Later in 2008, Chan _et al_. [12] presented a
new algorithm that improves the update time to $\tilde{\cal
O}\left({m^{2/3}}\right)$.

Holm _et al_. [27] in 1998 presented a deterministic algorithm for fully
dynamic connectivity on edge updates which takes amortized $\tilde{\cal
O}\left({1}\right)$ time per update and $\tilde{\cal O}\left({1}\right)$ time
per query. For the same problem, Kapron _et al_. [28] presented a Monte Carlo
algorithm with poly-logarithmic worst case bounds in 2013. Since switching the
state of a vertex is equivalent to ${\mathcal{O}}\left({{n}}\right)$ edge
updates, the algorithms by Holm _et al_ [27] and Kapron _et al_ [28] can be
used for the dynamic subgraph connectivity problem with the respective update
times multiplied by a factor of $n$.

The DFS-tree based algorithm by Baswana _et al_. [2] was the first
deterministic algorithm for dynamic subgraph connectivity with
$o\left({m}\right)$ worst case update time and a constant query time. In
addition to switching the state of existing vertices, it allows insertion of
new vertices as well. Their algorithm processes each update in
${\mathcal{O}}\left({{\sqrt{mn}\log^{2.5}{n}}}\right)$ and answers each query
in ${\mathcal{O}}\left({{1}}\right)$ time. The subsequent results by Chen _et
al_. [16] and Nakamura and Sadakane [31] for updating DFS trees also improve
the worst case update time and space occupied by the data structure for the
given problem. Using our dynamic DFS Tree algorithm, we extend the results of
[2, 16, 31] by improving the worst-case time complexity to
${\mathcal{O}}\left({{\sqrt{mn\log{n}}}}\right)$.

#### Our Algorithm

We maintain the DFS tree of the graph $G$. This tree is rooted at a dummy
vertex $r$ and other trees in the forest are hanging from the vertex $r$. To
check if any two vertices are connected in $G$, we find the lowest common
ancestor of the two vertices in the DFS tree. If the required ancestor is $r$,
then the pair is not connected in $G$. If any other vertex is the lowest
common ancestor, then the pair is connected. After each update, the DFS tree
can be refreshed in ${\mathcal{O}}\left({{\sqrt{mn\log{n}}}}\right)$ time.
This also enables us to answer the queries in
${\mathcal{O}}\left({{1}}\right)$ time.

###  A.2 Dynamic Subgraph Biconnectivity and Subgraph 2-edge Connectivity

#### Problem definition & Existing results

The structure and information stored in DFS trees also helps in solving
dynamic subgraph biconnectivity and subgraph 2-edge connectivity problems.
Baswana _et al_. [2] presented an
${\mathcal{O}}\left({{\sqrt{mn}\log^{2.5}n}}\right)$ worst case update time
and constant query time algorithm by augmenting their dynamic DFS algorithm.
We demonstrate how the new algorithm can be augmented on similar lines to
solve these problems as well.

A Biconnected Component in a graph $G$ is a maximal subgraph $S$ with the
following property - On failure of any vertex $v$ within $S$, subgraph
$S\setminus\\{v\\}$ remains connected. Similarly, a 2-edge Connected Component
is a maximal subgraph $S$ with the property - after failure of any edge $e$ in
the graph $G$, vertices in $S$ remain connected. In both the problems, the
input graph is partitioned into subgraphs, where each subgraph corresponds to
one such component. A query involves checking if a given pair of vertices lie
within the same component.

Another perspective to this partitioning is through Articulation points and
Bridges.

######  Definition 17.

Given an undirected graph $G=(V,E)$, a vertex $x\in V$ is an articulation
point iff there exists a pair of vertices $u$ and $v$, such that every path
from $u$ to $v$ passes through $x$.

######  Definition 18.

Given an undirected graph $G=(V,E)$, an edge $e\in E$ with endpoints $x,y\in
V$ is a bridge iff there doesn’t exist any path between $x$ and $y$ but the
one through edge $e$.

Articulation Points and Bridges act as boundaries between biconnected or
2-edge components, and thus partition the graph into a set of connected
components. Articulation Points and Bridges can be found using Depth First
Numbers. Using these DFNs, the high-point of each vertex is defined. The high-
point of any vertex $x$ is the smallest DFN $a$, such that either
$dfn\left({x}\right)=a$ or there is a back edge from $x$ or descendant of $x$
incident on a vertex $w$ such that $dfn\left({w}\right)=a$. Any non-root
vertex $x\in V$ is an articulation point if the high-point of any child of $x$
is $\geq dfn\left({x}\right)$. The root vertex is an articulation point if has
two or more children in $T$. Any tree edge $(x,y)$, with $x=par_{T}(y)$, is a
bridge iff the high-point of $y$ is $dfn\left({y}\right)$. Thus, one can find
the biconnected or 2-edge connected components in
${\mathcal{O}}\left({{m+n}}\right)$ time using DFS traversal. Moreover, if one
has the DFS tree $T$ and high-points of all the vertices, then the components
can be computed in ${\mathcal{O}}\left({{n}}\right)$ time.

#### Our Algorithm

We augment the new dynamic DFS algorithm such that it can compute the high-
points of all vertices while computing the new DFS tree $T^{*}$. To compute
the high-points of any vertex $x$, the static algorithm scans over the edges
incident on $x$. Instead of scanning over all the edges, we build a compact
list of edges that are sufficient to find the high-points. This list, let’s
call it $A$, is built while constructing the DFS Tree $T^{*}$ and satisfies
the following crucial property:

For every edge $(x,y)$ in the updated graph, where $x$ is an ancestor of $y$
in $T^{*}$, at-least one edge $(u,v)$ is present in $A$ such that $u$ is $x$
or an ancestor of $x$ in $T^{*}$ and $v$ is $y$ or a descendant of $y$ in
$T^{*}$.

List $A$ can be populated by incorporating the following to the Reroot
procedure. First, all new edges added to graph $G$ are added to $A$. Now
during the Reroot procedure, when the traversal enters the shallow tree node
$\nu$ at vertex $v$, and travels towards the farther endpoint, say vertex $y$,
following edges are added to $A$. Let $t$ be the vertex closest to root of $T$
among $v$ and $y$.

  1. 1.

For every unvisited descendant $d$ of $t$, the edge from $d$ to path
$v\rightarrow y$ incident closest to $v$, if any, is added.

  2. 2.

For every visited descendant $d$ of $t$, the edge from $d$ to path
$v\rightarrow y$ incident closest to $y$, if any, is added.

Let’s look at the time required to do the above. We need to iterate over all
descendants of vertex $t$ and find appropriate edges from descendants to
path$\left({v,y}\right)$ as according to above. This is very similar to
handling descendants while populating the reduced adjacency lists. Thus it
takes 2 queries to ${\cal D}$ to add the required edges to $A$. This doesn’t
change the time complexity of Reroot procedure. Moreover, instead of creating
another list $A$, we could simply add these edges to the reduced adjacency
lists ${\cal L}$ without increasing the size of ${\cal L}$ by anything more
than a constant.

Using these lists, we can find the high-points of all vertices in
${\mathcal{O}}\left({{n}}\right)$ time and thus update the components. The
time required per update is ${\mathcal{O}}\left({{\sqrt{mn\log{n}}}}\right)$,
which improves by a $log$ factor on the previous best by Chen _et al_. [16].
Also, compared to the augmentation used by [2], the changes which we introduce
are simple and minimal.

######  Theorem 19.

An undirected graph can be preprocessed in ${\mathcal{O}}\left({{m+n}}\right)$
time to build a data structure of ${\mathcal{O}}\left({{m+n}}\right)$ words,
which can be used to update the solutions for the dynamic subgraph
connectivity problem, dynamic subgraph biconnectivity problem, and subgraph
2-edge connectivity problem in
${\mathcal{O}}\left({{\sqrt{mn\log{n}}}}\right)$ time and to answer each query
in ${\mathcal{O}}\left({{1}}\right)$ time.

######  Remark 2.

There have been a couple of new results for dynamic subgraph connectivity
problems after [2] which improved the time bound in some special cases.
Nakamura [30] presented algorithms for dynamic subgraph connectivity which
achieve better update time when the number of leaf nodes in DFS Tree is
$o\left({n}\right)$. They presented an algorithm that achieves the amortized
update time
${\mathcal{O}}\left({{\sqrt{m}\log^{1.25}{n}+l\frac{\log^{2}{n}}{\log{\log{n}}}+n}}\right)$
and they also presented a Monte Carlo algorithm with worst-case
${\mathcal{O}}\left({{\sqrt{ml}\log^{2.75}{n}+n}}\right)$ update time. Here,
$l$ is the number of leaf nodes in the DFS tree of the input graph.

Another notable result is by Nanongkai _et al_. [32] in 2017. They presented a
Las Vegas algorithm to maintain minimum spanning forest which takes
${\mathcal{O}}\left({{n^{o\left({1}\right)}}}\right)$ worst-case time(w.h.p.)
to process general edge updates. This implicitly results in a Las Vegas
algorithm for dynamic subgraph connectivity with
${\mathcal{O}}\left({{n^{1+o\left({1}\right)}}}\right)$ time per vertex
update.

##  Appendix B Preprocessing to make $S$ and $D$

1Function  _DFS (node)_

2 $status(node)\leftarrow$ visited;

3 $size(node)\leftarrow 1$;

4 for  _$v\in\mathcal{N}\left({node}\right)$_ do

5 if  _status $\left({v}\right)$ is unvisited _ then
$D\left({v}\right)\leftarrow D\left({v}\right)\cup\\{node\\}$;

6

7 end for

8 for  _$v\in\mathcal{N}\left({node}\right)$_ do

9 if  _ $status(v)=unvisited$ _ then

10 $par_{T}\left({v}\right)\leftarrow node$;

11 $DFS(v)$;

12 $size(node)\leftarrow size(node)+size(v)$;

13

14 end if

15

16 end for

$heavy\\_child(node)\leftarrow\text{child with heaviest subtree}$ ;

/* Null if leaf-node */

17

18

Algorithm 3 To generate a DFS tree, get sizes of subtrees and find the
heaviest child

1Function  _Manipulate(v)_

2 $status(v)\leftarrow visited$;

3 $dfn(v)\leftarrow curr\\_time++$;

4 if  _$v$ is non-leaf_ then

5
stnode$\left({v}\right)\leftarrow\text{Manipulate}\left({heavy\\_child\left({v}\right)}\right)$;

6

7 else

8 stnode$\left({v}\right)\leftarrow\text{path}\left({v,v}\right)$;

$\mathcal{P}\leftarrow\mathcal{P}\cup\\{\text{stnode}\left({v}\right)\\}$ ;

/* New path with single vertex */

9

10 end if

11 Update $PathEndPoints$ for stnode$\left({v}\right)$;

12 foreach  _$x\in\mathcal{N}(v)$_ do * /* Iterate in order similar to DFS */

13 if  _$status(x)$ is unvisited_ then

$par_{S}\left({\text{Manipulate}\left({x}\right)}\right)\leftarrow\text{stnode}(v)$
;

/* Path with dashed edge */

14

15 end if

16

17 end foreach

18 return $\text{stnode}(v)$

19

Algorithm 4 Manipulates the $dfn$ and finds the endpoints of paths in
$\mathcal{P}$