# Space-Efficient Fully Dynamic DFS
## 3 Overview of the Algorithms of [PERSON] et al.
### Dynamic DFS Algorithm  
Next we refer to the algorithm for the dynamic DFS. [PERSON] et al. [4] proposed an algorithm for this problem by using the fault tolerant DFS algorithm as a subroutine. Their result can be summarized in the following lemma. **Lemma 2** ([4]). : _Suppose that for any \(k(\leq n)\) updates on an undirected graph \(G\), a new DFS tree can be built in \(O(kg+h)\) time with a data structure constructed in \(O(f)\) time (i.e., with \(O(f)\) preprocessing time). Then for any on-line sequence of updates on the graph, a new DFS tree after each update can be built in amortized/worst-case \(O(\sqrt{fg}+h)\) time per update, if \(\sqrt{f/g}\leq n\) holds._  
First we refer to the amortized (not worst-case) update time algorithm. Their idea is to rebuild the data structure \(\mathcal{D}\), which is constructed at the preprocessing in the fault tolerant DFS algorithm, periodically. To explain this idea in detail, let \(G_{j}\) be the graph obtained by applying first \(C_{j}:=c_{0}+\cdots+c_{j-1}\) updates on \(G\) (\(c_{1},c_{2},\ldots\) is later decided), \(n_{j}\) and \(m_{j}\) be the number of vertices and edges in \(G_{j}\), and \(T_{j}\) be the DFS tree for \(G_{j}\) reported by this algorithm. For the first \(c_{0}\) updates, use the data structure \(\mathcal{D}_{0}\) constructed from the original graph \(G\) and DFS tree \(T\). That is, after each arrival of graph update, we perform the fault tolerant DFS algorithm as if all previous updates come simultaneously. After \(c_{0}\) updates are processed, build the data structure \(\mathcal{D}_{1}\) from \(G_{1}\) and \(T_{1}\), and use \(\mathcal{D}_{1}\) for next \(c_{2}\) updates. In other words, from \((c_{0}+1)\)-st to \((c_{0}+c_{1})\)-th updates, we perform the fault tolerant DFS as if from \((c_{0}+1)\)-st to the latest updates come simultaneously. Similarly, after \(C_{j}\) updates are processed, the data structure \(\mathcal{D}_{j}\) is built from \(G_{j}\) and \(T_{j}\), and \(\mathcal{D}_{j}\) is used for next \(c_{j}\) updates. We call the moment \(\mathcal{D}_{j}\) is used _phase \(j\)_ of the amortized update time algorithm. In this way the construction time of the data structures is amortized over \(c_{j}\) updates in phase \(j\). Now suppose that for any \(k(\leq n)\) updates on \(G\), a new DFS tree can be built in \(O(kg_{j}+h_{j})\) time with \(\mathcal{D}_{j}\) built in \(O(f_{j})\) time, where \(f_{j},g_{j}\) and \(h_{j}\) are all functions of \(n_{j}\) and \(m_{j}\). Then the update time complexity becomes \(O(f_{j}/c_{j}+g_{j}c_{j}+h_{j})=O(\sqrt{f_{j}g_{j}}+h_{j})\) by setting \(c_{j}=\sqrt{f_{j}/g_{j}}\). Therefore, we can achieve the amortized update time bound in Lemma 2. Here in phase \(j\), \(f,g\) and \(h\) in Lemma 2 are indeed \(f_{j},g_{j}\) and \(h_{j}\), and are functions of \(n_{j}\) and \(m_{j}\). Next we proceed to the worst-case update time algorithm. The idea to achieve the efficient \"worst-case\" update time described in [4] is to actually divide the construction process of data structure over \(c_{j}\) updates. Here we assume that the number of edges is not dramatically changed during each phase, i.e., \(lm_{j}\leq m_{j+1}\leq lm_{j}\) holds for all \(j=1,2,\ldots\) with some constants \(l\) and \(h\). With this assumption we can say \(c_{j}\) and \(c_{j+1}\) differs only by a constant factor (since the number of vertices is not dramatically changed during each phase). In our algorithm described in Sections 5 and 7, we can say this assumption always holds on condition that \(n=o(m)\), so later we do not touch it. Let us go into detail. For the first \(c_{0}\) updates, use the data structure \(\mathcal{D}_{0}\) built from the original graph \(G\) and DFS tree \(T\). For the next \(c_{1}\) updates, use again \(\mathcal{D}_{0}\) and build \(\mathcal{D}_{1}\) gradually from \(G_{1}\) and \(T_{1}\).