# Recent Advances in Efficient Dynamic Graph Processing
## 4 Algorithms
### Path Traversal
#### 4.4.1 Depth-First Search  
Depth-first search (DFS) is a fundamental graph traversal technique. Starting from a root node, the algorithm exhaustively traverses each branch to its maximum depth before backtracking its steps. After [PERSON]'s groundbreaking contributions [150], DFS has become indispensable in solving core graph theory challenges, serving as the foundation for numerous algorithmic solutions such as strongly connected components [150], bipartite matching [151], biconnected components [152], and dominators in directed graphs [153]. **Definition 13** (Depth-first Search [154]). : _Given a directed graph \(G\), a depth-first search (DFS) traverses \(G\) in a particular order: starting from an initial vertex, it systematically visits unvisited out-neighbors until reaching a dead-end, then retraces its path to explore alternative branches._  
**Definition 14** (DFS-Tree [154]). : _Given a graph \(G\), a DFS-Tree of \(G\) is a spanning tree formed by the process of DFS._  
Given a directed graph \(G\) and any search spanning tree of \(G\), edges can be categorized as either tree edges or non-tree edges. The edges appearing in the tree are called tree edges. The remaining edges \((u,v)\) are non-tree edges that can be further classified into one of the following four types: (1) Forward edge: if \(u\) is an ancestor of \(v\) in the spanning tree. (2) Backward edge: if \(u\) is a descendant of \(v\) in the spanning tree. (3) Forward-cross edge: if \(u\) and \(v\) are unrelated in the tree, and \(u\) is visited before \(v\). (4) Backward-cross edge: if\(u\) and \(v\) are unrelated in the tree, and \(u\) is visited after \(v\). Figure 7 illustrates these edge classifications, which are fundamental to analyzing DFS-tree properties. For a graph \(G\) with \(n\) vertices and \(m\) edges, constructing a DFS-tree via depth-first search requires \(O(n+m)\)[154]. While DFS-tree computation is well-understood for static graphs, its dynamic maintenance remained largely unexplored until recent years. Early research focused on the ordered DFS-tree variant, with [156] establishing its P-completeness. Subsequent works [157; 158] demonstrate that such P-complete problems inherently resist efficient dynamic solutions. Specifically, Ref. [158] proves that any \(O(t(m,n))\)-time maintenance algorithm for ordered DFS-trees would imply that all problems in P could be maintained in \(O(t(m,n))\) time. Regarding the general DFS-Tree, initial progress includes [95]'s \(O(mn)\)-time incremental algorithm for DAGs and [98]'s expected \(O(mn\log n)\)-time decremental solution for DAGs. For undirected graphs, Ref. [96] achieves \(O(n^{2})\) total time for incremental updates. Despite these advances, all existing approaches remain limited to partially dynamic settings and fail to achieve sublinear \(o(m)\) worst-case update time, meaning they may degenerate to static recomputation complexity in worst-case scenarios. Ref. [94] presents the first fully dynamic DFS algorithm achieving sublinear \(O(m)\) update time. The algorithm leverages pre-update DFS-trees to construct reduced adjacency lists. Their approach achieves a worst-case update time of \(O(\sqrt{mn}\log^{2.5}n)\) for undirected graphs. Moreover, Ref. [94] also provides an incremental algorithm with an improved \(O(n\log^{3}n)\) bound for incremental cases. Building on this foundation, Ref. [91] further optimized these results to \(O(\sqrt{mn}\log^{2.5}n)\) for fully dynamic and \(O(n)\) for incremental settings. Building upon the framework in [94], Ref. [92] develops an enhanced algorithm achieving \(O(\sqrt{mn}\log^{0.75+\epsilon}n)\) update time for fully dynamic graphs and \(O(n\sqrt{\log n})\) for incremental cases, using \(O(m\log n)\) space. In [92], further optimizations reduce space to \(O((3m+o(m))\log n)\) while maintaining a worst-case update time of \(O(\sqrt{mn}\log^{1.25}n)\) for thee fully dynamic setting and \(O(n\log n)\) for the incremental setting. Ref.