Fine-Grained Optimality of Partially Dynamic Shortest Paths and More

Single Source Shortest Paths (SSSP) is among the most well-studied problems in computer science. In the incremental (resp. decremental) setting, the goal is to maintain distances from a fixed source in a graph undergoing edge insertions (resp. deletions). A long line of research culminated in a near-optimal deterministic (1 + ε)-approximate data structure with m 1+o(1) total update time over all m updates by Bernstein, Probst Gutenberg and Saranurak [FOCS 2021]. However, there has been remarkably little progress on the exact SSSP problem beyond Even and Shiloach's algorithm [J. ACM 1981] for unweighted graphs. For weighted graphs, there are no exact algorithms beyond recomputing SSSP from scratch in O(m 2 ) total update time, even for the simpler Single-Source Single-Target Shortest Path problem (stSP). Despite this lack of progress, known (conditional) lower bounds only rule out algorithms with amortized update time better than m 1/2-o(1) in dense graphs.

In this paper, we give a tight (conditional) lower bound: any partially dynamic exact stSP algorithm requires m 2-o(1) total update time for any sparsity m. We thus resolve the complexity of partially dynamic shortest paths, and separate the hardness of exact and approximate shortest paths, giving evidence as to why no non-trivial exact algorithms have been obtained while fast approximation algorithms are known.

Moreover, we give tight bounds on the complexity of combinatorial algorithms for several path problems that have been studied in the static setting since early sixties: Node-weighted shortest paths (studied alongside edge-weighted shortest paths), bottleneck paths (early work dates back to 1960), and earliest arrivals (early work dates back to 1958). These bounds rule out any nontrivial combinatorial algorithms for these problems in the partially dynamic setting. Interestingly, for all of the above path-variant problems, we obtain faster partially dynamic algorithms using fast matrix multiplication.