Deterministic Fully Dynamic SSSP and More
Preprint
Abstract
We present the first non-trivial fully dynamic algorithm maintaining exact single-source distances in unweighted graphs. This resolves an open problem stated by Sankowski [COCOON 2005] and van den Brand and Nanongkai [FOCS 2019]. Previous fully dynamic single-source distances data structures were all approximate, but so far, non-trivial dynamic algorithms for the exact setting could only be ruled out for polynomially weighted graphs (Abboud and Vassilevska Williams, [FOCS 2014]). The exact unweighted case remained the main case for which neither a subquadratic dynamic algorithm nor a quadratic lower bound was known. Our dynamic algorithm works on directed graphs, is deterministic, and can report a single-source shortest paths tree in subquadratic time as well. Thus we also obtain the first deterministic fully dynamic data structure for reachability (transitive closure) with subquadratic update and query time. This answers an open problem of van den Brand, Nanongkai, and Saranurak [FOCS 2019]. Finally, using the same framework we obtain the first fully dynamic data structure maintaining all-pairs $(1+ε)$-approximate distances within non-trivial sub-$n^ω$ worst-case update time while supporting optimal-time approximate shortest path reporting at the same time. This data structure is also deterministic and therefore implies the first known non-trivial deterministic worst-case bound for recomputing the transitive closure of a digraph.
Keywords
All Related Versions
This publication has 45 references indexed in Scilit:
- On Dynamic Shortest Paths ProblemsAlgorithmica, 2010
- Fast Dynamic Transitive Closure with LookaheadAlgorithmica, 2008
- Mantaining Dynamic Matrices for Fully Dynamic Transitive ClosureAlgorithmica, 2007
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest pathsJournal of Algorithms, 2007
- A Fully Dynamic Algorithm for Maintaining the Transitive ClosureJournal of Computer and System Sciences, 2002
- Fast Rectangular Matrix Multiplication and ApplicationsJournal of Complexity, 1998
- Incremental algorithms for minimal length pathsJournal of Algorithms, 1991
- A balanced search tree with O(1) worst-case update timeActa Informatica, 1988
- Amortized efficiency of a path retrieval data structureTheoretical Computer Science, 1986
- Efficient determination of the transitive closure of a directed graphInformation Processing Letters, 1971