Abstract
The Single-Source Shortest Path (SSSP) problem is a cornerstone of graph theory. While randomized algorithms have achieved subquadratic update times in fully dynamic graphs, deterministic solutions have remained stuck at the trivial $O(n^2)$ recomputation limit for decades. This paper introduces the first deterministic, subquadratic algorithm for exact SSSP in unweighted graphs, achieving an update time of $O(n^{1.969})$. By integrating dynamic matrix inverse techniques with a novel deterministic hitting set construction, the authors overcome the limitations of previous algebraic approaches.
Introduction
In the fully dynamic Single-Source Shortest Path (SSSP) problem, the goal is to maintain the distances from a fixed source vertex to all other vertices in a graph subject to edge insertions and deletions. For unweighted graphs with $n$ vertices, the simplest approach is to re-run a Breadth-First Search (BFS) after every update, which requires $O(n^2)$ time in dense graphs.
Breaking this $O(n^2)$ "quadratic barrier" deterministically has been a major open problem in the field of dynamic graph algorithms for over twenty years. While randomized algorithms—which often rely on the assumption of an oblivious adversary—have achieved subquadratic bounds, deterministic algorithms are required for robustness against adaptive adversaries. This paper presents a breakthrough by providing a deterministic algorithm that maintains exact distances in $O(n^{1.969})$ time per update.
Methodology
The authors' approach is fundamentally algebraic, reducing graph-theoretic path problems to matrix operations. The framework is built upon several key technical innovations.
1. Dynamic Matrix Inverse and Path Counting
The algorithm represents the graph using an adjacency matrix and relates path counting to the inversion of a specific matrix (typically $I - xA$) over a ring of power series. To handle edge updates, the authors utilize the Sherman-Morrison and Woodbury identities. These identities allow for the efficient update of a matrix inverse when the underlying matrix undergoes low-rank changes, such as adding or removing an edge.
2. Phased Rebuilding
To maintain efficiency, the algorithm operates in discrete phases of $\Delta$ updates. At the beginning of each phase, the algorithm performs a more expensive "rebuild" to establish a robust set of paths. During the phase, the algebraic data structure tracks how subsequent edge updates affect these paths. This prevents the computational cost of the matrix operations from escalating with every single change.
3. Deterministic Hitting Sets
A common technique in randomized shortest-path algorithms is the use of a "hitting set"—a small subset of vertices that intersects every sufficiently long path. Traditionally, these sets are chosen randomly. The authors derandomize this process by shifting the focus: instead of trying to maintain a hitting set for all paths in a constantly changing graph, they compute a deterministic hitting set for a fixed collection of paths identified at the start of a phase. This "static hitting set" approach allows the algorithm to maintain subquadratic performance without relying on probability.
4. Path Reporting via Blocking
Beyond merely calculating distances, the paper addresses the problem of path reporting. By grouping vertices into blocks, the authors can identify predecessor vertices in the shortest path tree in subquadratic time. This allows the algorithm to output the actual paths, a feature often missing from purely algebraic distance-maintenance schemes.
Key Results and Analysis
The primary contribution is the deterministic SSSP algorithm, but the framework yields several other significant results:
- Deterministic SSSP: The algorithm achieves a worst-case update and query time of $O(n^{1.969})$. This marks the first time the $O(n^2)$ barrier has been broken deterministically for exact distances in unweighted graphs.
- Randomized Improvement: By allowing for randomization, the authors further optimize the bound to $O(n^{1.933})$.
- Approximate All-Pairs Shortest Paths (APSP): The paper provides a deterministic algorithm for $(1+\epsilon)$-approximate APSP with an update time of $O(n^{2.293}/\epsilon)$. This is notably faster than the $O(n^\omega)$ time required for recomputation from scratch, where $\omega \approx 2.37$ is the exponent of fast matrix multiplication.
- Transitive Closure: The authors demonstrate that for any $\omega > 2$, there exists a deterministic algorithm for transitive closure (reachability) that is strictly faster than $O(n^\omega)$.
Discussion and Future Work
While this work represents a theoretical milestone, it has specific limitations. The results are primarily applicable to unweighted or small-integer weighted graphs. Extending these deterministic subquadratic bounds to graphs with large, arbitrary weights is a significant challenge, as the APSP conjecture suggests such bounds might be impossible for the general case.
Furthermore, like many algorithms based on fast matrix multiplication, the hidden constants in the $O$-notation are likely high. In practice, traditional BFS or Dijkstra's algorithm may still be faster for smaller graphs or specific graph topologies. Future research will likely focus on narrowing the gap between the $O(n^{1.969})$ bound and the theoretical lower bounds, potentially pushing the exponent closer to $1.5$.
Conclusion
By successfully derandomizing the hitting set construction and refining the use of dynamic matrix inverses, the authors have resolved a long-standing challenge in dynamic graph algorithms. This work not only provides a faster way to maintain shortest paths but also deepens the connection between algebraic matrix techniques and combinatorial graph problems.
Summary updated