# Space-Efficient Fully Dynamic DFS
### Our Results  
We develop algorithms for incremental (i.e., under edge insertions) and fully dynamic (i.e., under edge/vertex insertions/deletions) DFS problems in undirected graphs, based on the algorithms [PERSON] et al. [4] proposed (an overview of their algorithms is in Section 3). The dynamic DFS algorithms of both [PERSON] et al. [4] and [PERSON] et al. [5; 7] require \(O(m\log^{2}n)\) bits of space, which is \(O(\log n)\) times larger than the space usage of the adjacency list of the graph \(G\) and thus do not seem to be optimal. Thus, we seek to compress the required space of the dynamic DFS.  
Besides this, we focus on relatively dense graphs, i.e., graphs with \(n=o(m)\), because in sparse graphs, i.e., \(m=O(n)\), DFS can be performed in \(O(n)\) time, which meets the conditional lower bound [PERSON] et al. [6] suggests. Here please note that they showed an example of a graph in which any dynamic DFS algorithm under edge update takes \(\Omega(n)\) time. Since this graph has only \(O(n)\) edges, the (conditional) lower bound holds even for the sparse graphs.  
We develop two algorithms for the dynamic DFS algorithm, namely algorithms A and B. Algorithm A is a simple modification of the work of [PERSON] et al. [4], while algorithm B is designed to reduce the space usage more and more. The comparison of the required space and worst-case update time of these algorithms with those of [PERSON] et al. [4] and [PERSON] et al. [5; 7] is given in Table 1. Both of our algorithms compress the required space by a factor of \(O(\log n)\) and improve the worst-case update time by a \(\mathrm{polylog}(n)\) factor under the fully dynamic case (i.e., supporting all four types of updates). Even under the incremental case (i.e., supporting only edge insertions), the update time is improved from [4], and close to [7]. Our main ingredient is the space usage of algorithm B: it is asymptotically only 1.5 times as much space as that of the adjacency list of \(G\). Here note that since \(G\) is undirected, the adjacency list of \(G\) should have two elements for each edge in \(G\) and thus requires \(2m\log n\) bits of space. We also show that if amortized update time is permitted instead of worst-case update time, the required space of algorithm B can be reduced to only \((2m+o(m))\log n\) bits.  
Here note that the new dynamic DFS algorithm of [PERSON] et al. [11] does not subsume algorithm B in terms of the space usage. However, it subsumes algorithm A because the space usage is the same, but the update time is faster. Even so, we describe the details of algorithm A in this paper because, as described below, our algorithm A (as well as algorithm B) can be applied to dynamic biconnectivity and 2-edge-connectivity problems including vertex insertions and deletions.  
Our work can be summarized as follows. First, we improve the way to solve a query that is frequently used in the algorithm of [PERSON] et al. [4] (Section 4), by using the idea of [PERSON] et al. [5] partially. By this improvement, we propose a linear space (i.e., requiring \(O(m\log n)\) bits of space) algorithm, algorithm A, for the incremental and fully dynamic DFS problems (Theorem 1 in Section 5). Second, we further compress the data structures used in [4; 5] using _wavelet tree_[12] (Section 6). In this contribution, we develop an efficient method for solving a kind of query on integer sequences, named _range leftmost (rightmost) value query_, and give a space-efficient method for solving a variant of _orthogonal range search problems_, which has been studied in the computational geometry community. These queries are of independent interest. Third, we consider a space-efficient method to implement the algorithm of [PERSON] et al. [4] (Section 7). By combining them, we propose a more space-efficient algorithm with worst-case update time, algorithm B, for the incremental and fully dynamic DFS problems (Theorems 4 and 5). Simultaneously, results for the amortized update time algorithms are also obtained (Theorems 2 and 3).