# Space-Efficient Fully Dynamic DFS
## 7 More Space-Efficient Dynamic DFS
### Amortized Update Time Dynamic DFS  
Next, we focus on the amortized update time dynamic DFS algorithm. During the \"amortized time\" algorithm described in Section 3.2, we should perform the reconstruction of the data structure \(\mathcal{D}\) to solve the fault tolerant DFS problem besides the fault tolerant DFS itself, and store information of up to last \(c\) updates. Here \(\mathcal{D}\) is indeed a bit vector and a wavelet tree described in Section 6. Therefore, we must consider (a) how many edges the reduced adjacency list \(L\) may have, (b) how much space is required to store information of updates, and (c) how to rebuild the data structure space-efficiently. We analyze these issues one by one. First we consider (a). Since we rebuild \(\mathcal{D}\) periodically, we solve the fault tolerant DFS problem with at most \(c_{j}\) updates in phase \(j\). Therefore, we can obtain an upper bound on the number of edges in \(L\). Under the incremental case, we can say \(f=m\sqrt{\log n},\ g=\sqrt{\log n}\) and \(h=n\log n\) for Lemma 2 (here \(\sqrt{f/g}=\sqrt{m}\leq n\) holds), and the size of \(L\) is bounded by \(O(n)\), as described in Section 7.1. Under the fully dynamic case, we can say \(f=m\sqrt{\log n},\ g=n\log^{2}n\) and \(h=0\), thus the upper bound is \(O(n\log n\cdot\sqrt{f/g})=O(\sqrt{mn}\log^{0.25}n)\) which is \(o(m)\) under the assumption \(m=\omega(n\log^{0.5}n)\). Hence we can conclude that \(L\) takes only \(o(m)\log n\) bits under any conditions. Next we consider (b), but this is almost the same as (a). Under the incremental case, the number of edges inserted during \(c_{j}\) updates is up to \(\sqrt{f/g}=\sqrt{m}\) which is \(o(m)\). Under the fully dynamic case, the number of edges inserted or deleted during \(c_{j}\) updates is up to \(O(n\sqrt{f/g})=O(\sqrt{mn}/\log^{0.75}n)\), since insertion or deletion of one vertex involves those of \(O(n)\) incident edges. This is smaller than the maximum size of \(L\), and thus it does not affect the bound. Please note that in the analysis of (a) and (b), we write \(n_{j},m_{j},f_{j},g_{j},h_{j}\) in Section 3.2 as \(n,m,f,g,h\) for simplicity. Finally, we consider (c). Let \(\mathcal{L}_{j}\) be the order of vertices in \(G_{j}\) defined by the pre-order traversal of \(T_{j}\), where \(G_{j}\) and \(T_{j}\) are the graph and its reported DFS tree at the beginning of phase \(j\) of the amortized update time algorithm, and let \(\mathcal{G}_{j}\) be the grid like \(\mathcal{G}\) constructed from \(G_{j}\) and \(\mathcal{L}_{j}\) (in our algorithm we do not retain \(\mathcal{G}_{j}\), but it helps the description of our algorithm clear). In addition to these, let \(S_{j}[1...m_{j}]\) and \(B_{j}\) be an integer sequence and a bit vector built from the upper (or lower) triangular part of \(\mathcal{G}_{j}\) in the same manner as Section 6 (in Section 6, they are written as \(S_{u}\) and \(B_{u}\) (or \(S_{l}\) and \(B_{l}\))). Now we focus on the end of phase \(j\), i.e., the time \(T_{j+1}\) is reported. Using these symbols, the rebuilding process at this moment is briefly described as follows. First, the order of vertices \(\mathcal{L}_{j+1}\) is decided according to the pre-order traversal of \(T_{j+1}\), and information attached to each vertex and edge of \(T_{j+1}\) is initialized. Second, a grid \(\mathcal{G}_{j+1}\) is considered, and \(S_{j+1}\) and \(B_{j+1}\) are built. Finally, a wavelet tree \(\mathcal{W}_{j+1}\) for \(S_{j+1}\) is constructed. The main difficulty in this rebuilding process is that the whole adjacency list is not retained. That means the information of all edges in \(G_{j+1}\) is not explicitly stored at this moment. It is stored in the wavelet tree \(\mathcal{W}_{j}\) for \(S_{j}\), the bit vector \(B_{j}\), and the information of the last \(c_{j}\) updates. In our algorithm, we additionally retain the integer sequence \(S_{j}\) during phase \(j\) of the algorithm. Then the main job in this moment is to construct \(S_{j+1}\) and \(B_{j+1}\) from \(S_{j}\), \(B_{j}\) and the information of last \(c_{j}\) updates.