# Space-Efficient Fully Dynamic DFS
## 3 Overview of the Algorithms of [PERSON] et al.
### Fault Tolerant DFS Algorithm  
We first refer to the algorithm for _fault tolerant DFS problem_. This problem is described as follows: given an undirected graph \(G\) and its DFS tree \(T\), we try to rebuild a DFS tree for the new graph obtained by deleting \(k(\leq n)\) edges and vertices (simultaneously) from \(G\). In this part \(U\) denotes a set of vertices and edges we want to delete from \(G\), and \(G-U\) denotes the new graph obtained by deleting vertices and edges in \(U\) from \(G\). Their algorithm uses a partitioning technique which divides a DFS tree into connected paths and subtrees. This partitioning is called _disjoint tree partitioning_ (DTP). **Definition 1** ([4]). : _A DFS tree \(T\) of an undirected graph \(G\) and a set \(U\) of vertices and edges are given, and the forest \(T-U\) obtained by removing the vertices and edges in \(U\) from \(T\) is considered. Given a vertex subset \(A\) of \(T-U\), a disjoint tree partitioning of \(T-U\) defined by \(A\) is a partition of a subgraph of \(T-U\) induced by \(A\) into a set \(\mathcal{P}\) of paths with \(|\mathcal{P}|\leq|U|\) and a set \(\mathcal{T}\) of trees. Here each \(p\in\mathcal{P}\) is an ancestor-descendant path in \(T\) and each \(\tau\in\mathcal{T}\) is a subtree of \(T\)._  
Using DTP, their algorithm can be summarized as follows. First, the DTP of \(T-U\) defined by \(V\setminus\{r\}\) (where \(V\) is the vertex set of \(T-U\) and \(r\) is the virtual vertex in Section 2) is calculated. As a result, a set \(\mathcal{P}\) of paths and a set \(\mathcal{T}\) of subtrees are constructed. Now let \(T^{*}\) be the partially constructed DFS tree of \(G-U\), and at first \(T^{*}\) contains only \(r\). Then their algorithm can be seen as if performing a static DFS traversal (start with \(r\)) on the graph whose vertex set is \(\mathcal{P}\cup\mathcal{T}\). When a path or a subtree \(x\in\mathcal{P}\cup\mathcal{T}\) is visited during the traversal, the algorithm extracts an ancestor-descendant path \(p^{*}\) from \(x\) and attaches it to \(T^{*}\), which means the vertices of \(p^{*}\) are marked as visited. Thereafter, the DTP of \(T-U\) defined by the unvisited vertices is recalculated. This can be performed by local operations around \(x\). More specifically, if \(x\in\mathcal{T}\) the remaining part \(x\setminus p^{*}\) is divided into some subtrees and they are stored in \(\mathcal{T}\); otherwise \(x\setminus p^{*}\) is an ancestor-descendant path and is pushed back to \(\mathcal{P}\). Then the traversal continues. If all vertices are visited, \(T^{*}\) is indeed the DFS tree of \(G-U\). The key point of reducing computational complexity is that taking advantage of partitioning, the number of edges accessed by this algorithm can be decreased from \(m\). At this time, it must be ensured that the edges not accessed by this algorithm are not needed to construct the new DFS tree \(T^{*}\). To achieve this, they use a _reduced adjacency list_\(L\) and two kinds of queries \(Q\) and \(Q^{\prime}\). Here \(Q\) and \(Q^{\prime}\) are defined as follows. **Definition 2** ([4]). : _A connected undirected graph \(G\), its DFS tree \(T\), and a set \(U\) of vertices and edges are given. Then for any three vertices \(w,x,y\) in \(G-U\), the following queries are considered. Among all edges in \(G-U\) which directly connect a subtree \(T(w)\) and an ancestor-descendant path \(path(x,y)\), \(Q(T(w),x,y)\) returns one of the edges whose endpoint on \(path(x,y)\) is the nearest to \(x\). Similarly, among all edges in \(G-U\) which directly connect a vertex \(w\) and an ancestor-descendant path \(path(x,y)\), \(Q^{\prime}(w,x,y)\) returns one of the edges whose endpoint on \(path(x,y)\) is the nearest to \(x\). If there are no connecting edges, these queries should return \(\emptyset\).