# Space-Efficient Fully Dynamic DFS
## 5 Linear Space Dynamic DFS
\(\mathcal{R}^{\prime}\) can also be built directly from the adjacency list of \(G\), and the ORP query on \(\mathcal{G}\) can be converted to the ORS query on \(\mathcal{R}^{\prime}\) in the same manner as described above. Figure 3 is an example of an undirected graph \(G\) and its corresponding rank space \(\mathcal{R}\). In this example, the rectangles \([1,3]\times[4,5]\) and \([4,5]\times[1,3]\) have a point inside, which corresponds to the edge connecting \(0\) and \(1\). Conversely, the rectangles \([1,3]\times[6,7]\) and \([6,7]\times[1,3]\) do not have a point inside, which indicates the absence of the edge connecting \(0\) and \(2\). Combining Lemma 4 with Lemma 3 implies the following corollary. **Corollary 1**. : _There exists a data structure of \(O(m\log n)\) bits such that for any \(w,x,y\), \(Q(T(w),x,y)\) can be solved in \(O(\log^{\epsilon}n)\) time and \(Q^{\prime}(w,x,y)\) in \(O(\log^{1+\epsilon}n)\) time. This data structure can be built in \(O(m\sqrt{\log n})\) time._  
This corollary directly gives a fault tolerant DFS algorithm when combining with Lemma 1. Here we must consider the space requirement of this algorithm, but it is simple. Information used in the algorithm other than the data structure to solve \(Q\) and \(Q^{\prime}\) and the reduced adjacency list \(L\) takes only \(O(n\log n)=o(m)\log n\) bits: there are \(O(n)\) words of information for the original DFS tree \(T\) (including the data representing the disjoint tree partition), \(O(1)\) words of information attached to each vertex and each edge in \(T\), a stack which has at most \(O(n)\) elements, and a partially constructed DFS  
Figure 3: An example of an undirected graph with vertex numbering, its adjacency list, and the corresponding rank space \(\mathcal{R}\). tree, but these sum up to only \(O(n)\) words. Moreover, since the reduced adjacency list \(L\) contains at most \(O(m)\) edges, the required space for \(L\) is bounded by \(O(m\log n)\) bits. From Corollary 1, the data structure to solve \(Q\) and \(Q^{\prime}\) occupies \(O(m\log n)\) bits. Hence the following lemma holds. An undirected graph \(G\) and its DFS tree \(T\) are given. Then there exists an algorithm such that with \(O(m\sqrt{\log n})\) preprocessing time, a DFS tree for the graph obtained by applying any \(k(\leq n)\) edge insertions to \(G\) can be built in \(O(n\log^{\varepsilon}n)\) time. Similarly, there exists an algorithm such that with \(O(m\sqrt{\log n})\) preprocessing time, a DFS tree for the graph obtained by applying any \(k(\leq n)\) updates (vertex/edge insertions/deletions) to \(G\) can be built in \(O(nk\log^{1+\varepsilon}n)\) time. These algorithms require \(O(m\log n)\) bits of space. Linear space dynamic DFS algorithms are obtained by combining Lemma 5 with Lemma 2. For the incremental case, we set \(f=m\sqrt{\log n}\), \(g=m\sqrt{\log n}/n^{2}\) and \(h=n\log^{\varepsilon}n\) for Lemma 2 (here the condition \(\sqrt{f/g}\leq n\) must be satisfied). Then the update time is \(O(\sqrt{fg}+h)=O(m/n\cdot\sqrt{\log n}+n\log^{\varepsilon}n)\). We can say the update time is \(O(n\log^{\varepsilon}n)\) if \(m=O(n^{2}/\sqrt{\log n})\), or \(O(n\sqrt{\log n})\) otherwise. For the fully dynamic case, we set \(f=m\sqrt{\log n}\), \(g=n\log^{1+\varepsilon}n\) and \(h=0\), and, therefore, the update time is \(O(\sqrt{mn}\log^{0.75+\varepsilon}n)\). There exists an algorithm such that given an undirected graph \(G\) and its DFS tree \(T\), for any on-line sequence of updates on \(G\), a new DFS tree after each update can be built in worst-case \(O(m/n\cdot\sqrt{\log n}+n\log^{\varepsilon}n)\) time per update under the incremental case, and \(O(\sqrt{mn}\log^{0.75+\varepsilon}n)\) time per update under the fully dynamic case, where \(0<\varepsilon<1/2\) is an arbitrary constant. This algorithm requires \(O(m\log n)\) bits.