Abstract
Depth first search (DFS) tree is one of the most well-known data structures for designing efficient graph algorithms. Given an undirected graph $G=(V,E)$ with $n$ vertices and $m$ edges, the textbook algorithm takes $O(n+m)$ time to construct a DFS tree. In this paper, we study the problem of maintaining a DFS tree when the graph is undergoing incremental updates. Formally, we show: Given an arbitrary online sequence of edge or vertex insertions, there is an algorithm that reports a DFS tree in $O(n)$ worst case time per operation, and requires $O\left(\min\{m \log n, n^2\}\right)$ preprocessing time. Our result improves the previous $O(n \log^3 n)$ worst case update time algorithm by Baswana et al. and the $O(n \log n)$ time by Nakamura and Sadakane, and matches the trivial $\Omega(n)$ lower bound when it is required to explicitly output a DFS tree. Our result builds on the framework introduced in the breakthrough work by Baswana et al., together with a novel use of a tree-partition lemma by Duan and Zhan, and the celebrated fractional cascading technique by Chazelle and Guibas.
Introduction
Depth First Search (DFS) is a fundamental technique in graph theory, serving as the backbone for algorithms ranging from planarity testing to identifying strongly connected components. While constructing a DFS tree in a static graph is a solved problem with the textbook $O(n + m)$ algorithm, real-world applications often involve dynamic graphs that evolve over time through edge or vertex insertions.
In such incremental settings, recomputing the DFS tree from scratch for every update is computationally expensive. The challenge lies in maintaining a valid DFS tree efficiently as the graph grows. Since any algorithm that explicitly outputs a DFS tree must at least list its $n-1$ edges, the theoretical lower bound for this task is $\Omega(n)$. Previous research has approached this bound with update times of $O(n \log^3 n)$ and $O(n \log n)$, but the optimal $O(n)$ worst-case bound remained elusive until now.
Methodology
The proposed algorithm builds upon the "Batch Insertion" framework. Rather than processing updates in isolation, the method analyzes how a sequence of insertions impacts the existing tree structure. The primary difficulty in incremental DFS is "rerooting": when a new edge is added, certain subtrees may need to be detached and re-attached to maintain the DFS property—specifically, that all non-tree edges in an undirected graph must be back-edges.
To achieve $O(n)$ worst-case time, the authors employ three sophisticated data structures to handle queries for the "highest" connection points of hanging subtrees:
- 2D Range Trees: These handle individual queries in $O(\log n)$ time by mapping graph edges to points in a 2D plane.
- Quadratic Space Lookup: For smaller or denser components, an $O(n^2)$ structure provides $O(1)$ query time.
- Tree-Partitioning and Fractional Cascading: This is the core innovation. By applying a tree-partitioning lemma to break the tree into manageable chunks and utilizing fractional cascading—a technique typically found in computational geometry—the algorithm can process "bundles" of queries. This allows the system to find the highest incident edges across entire paths simultaneously, effectively reducing the amortized cost per query to $O(1)$.
Theoretical Analysis
As a theoretical contribution, the algorithm's performance is verified through rigorous asymptotic analysis. The key results include:
- Optimal Update Time: The algorithm achieves $O(n)$ worst-case time per insertion, matching the trivial lower bound for outputting the tree.
- Efficient Preprocessing: Initialization requires $O(\min\{m \log n, n^2\})$ time and space, making it competitive with static construction in many scenarios.
- De-amortization: The authors utilize a de-amortization technique to transform the naturally amortized batch process into a strict worst-case guarantee for every single update, ensuring smooth performance even under adversarial update sequences.
Conclusion and Future Work
This work successfully closes the complexity gap for incremental DFS in undirected graphs, reaching the theoretical speed limit. However, several open problems remain. The current techniques rely heavily on the "back-edge" property unique to undirected DFS trees, meaning they do not directly translate to directed graphs. Furthermore, the algorithm is strictly incremental; handling deletions (the "fully dynamic" case) remains a significantly more complex challenge, as current fully dynamic DFS algorithms are still significantly slower than the $O(n)$ efficiency achieved here for insertions.
Summary updated