# Space-Efficient Fully Dynamic DFS
## 2 Preliminaries  
Throughout this paper, \(n\) denotes the number of vertices and \(m\) denotes the number of edges. We assume that a graph is always simple, i.e., has no self-loops or parallel edges, since they make no sense in constructing DFS tree. With this assumption we can conclude \(m=O(n^{2})\) and \(\log m=O(\log n)\). We also assume that \(n=o(m)\). We use \(\log(\cdot)\) as the base-2 logarithm. From now, the term \"fully dynamic setting\" includes vertex updates as well as edge updates, while \"incremental setting\" includes only edge insertions. Given an undirected graph \(G\) and its DFS tree (forest) \(T\), the parent vertex of a vertex \(v\) in \(T\) is denoted by \(par(v)\). A _subtree_ of \(T\) rooted at \(v\) is the subgraph of \(T\) induced by \(v\) and its descendants, and is denoted by \(T(v)\). Two vertices \(x\) and \(y\) are said to have _ancestor-descendant relation_ iff \(x=y\), \(x\) is an ancestor of \(y\), or \(y\) is an ancestor of \(x\). The path in \(T\) connecting two vertices \(x\) and \(y\) is denoted by \(path(x,y)\). A path \(p\) in \(T\) is called an _ancestor-descendant path_ iff the endpoints of \(p\) have ancestor-descendant relation. Given a connected undirected graph \(G\) and its rooted spanning tree \(T\), non-tree edges, i.e., the edges in \(G\) which are not included in \(T\), can be classified into two types. A non-tree edge is called a _back edge_ if it connects two vertices which have ancestor-descendant relation; otherwise it is called a _cross edge_. Then \(T\) is a DFS tree of \(G\) iff all non-tree edges are back edges. We call this _DFS property_. We can assume that the graph \(G\) is always connected by the following way. At the beginning, we add a virtual vertex \(r\), and edges \((r,v)\) for all vertices \(v\) in \(G\), to the graph \(G\). During our algorithm, we keep a DFS tree of this augmented graph rooted at \(r\). The DFS tree (forest) of the original graph can be obtained by simply removing \(r\) from the DFS tree of the augmented graph. **Bit Vectors. ** Let \(B[1...l]\) be a 0,1-sequence of length \(l\), and consider two queries on \(B\): for \(c=0,1\), \(\mathtt{rank}_{c}(i,B)\) returns the number of occurrences of \(c\) in \(B[1...i]\), and \(\mathtt{select}_{c}(i,B)\) returns the position of the \(i\)-th occurrence of \(c\) in \(B\) if exists or \(\emptyset\) otherwise. Then there exists a data structure such that \(\mathtt{rank}\) and \(\mathtt{select}\) queries for \(c=0,1\) can both be answered in \(O(1)\) time and the required space is \(l+O(l\log\log l/\log l)=l+o(l)\) bits [15; 16]. Moreover, the space can be reduced to \(lH_{0}(B)+o(l)\) bits while keeping \(O(1)\) query time [17], where \(H_{0}(B)\leq 1\) is the zeroth-order empirical entropy of \(B\). When 1 occurs \(k\) times in \(B\), \(lH_{0}(B)=k\log\frac{l}{k}+(l-k)\log\frac{l}{l-k}\leq k\log\frac{l}{k}\). **Wavelet Trees. ** Let \(S[1...l]\) be an integer sequence of symbols \([0,\sigma-1]\). A wavelet tree [12] for \(S\) is a complete binary tree with \(\sigma\) leaves and \(\sigma-1\) internal nodes, each internal node of which has a bit vector [15; 16]. Each node \(v\) corresponds to an interval of symbols \([l_{v},r_{v}]\subseteq[0,\sigma-1]\); the root corresponds to \([0,\sigma-1]\) and its left (right) child to \([0,\lfloor\sigma/2\rfloor]\) (\([\lfloor\sigma/2\rfloor+1,\sigma-1]\)), and these intervals are recursively divided until leaves, each of which corresponds to one symbol. The bit vector \(B_{v}[1...L_{v}]\) corresponding to an internal node \(v\) is defined as follows. Let \(S_{v}[1...L_{v}]\) be the subsequence of \(S\) which consists of elements with symbols \([l_{v},r_{v}]\). Then if the symbol \(S_{v}[i]\) corresponds to the left child of \(v\) then \(B_{v}[i]=0\); otherwise \(B_{v}[i]=1\). The wavelet tree requires \((l+o(l))\log\sigma\) bits of space, and can be built in \(O(l\log\sigma/\sqrt{\log l})\) time [18].