Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

Abstract

We study dynamic $(1+\epsilon )$-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected $n$-node $m$-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of $\tilde{O}(mn/\epsilon )$ and constant query time by Roditty and Zwick [FOCS 2004]. The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach [JACM 1981]; it has a total update time of $O(m{n}^2)$ and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of $\tilde{O}(n^{5/2}/\epsilon )$ and constant query time that has an additive error of $2$ in addition to the $1+\epsilon$ multiplicative error. This beats the previous $\tilde{O}(mn/\epsilon )$ time when $m=\Omega (n^{3/2})$. Note that the additive error is unavoidable since, even in the static case, an $O(n^{3-\delta })$-time (a so-called truly subcubic) combinatorial algorithm with $1+\epsilon$ multiplicative error cannot have an additive error less than $2-\epsilon$, unless we make a major breakthrough for Boolean matrix multiplication [Dor et al. FOCS 1996] and many other long-standing problems [Vassilevska Williams and Williams FOCS 2010]. The algorithm can also be turned into a $(2+\epsilon )$-approximation algorithm (without an additive error) with the same time guarantees, improving the recent $(3+\epsilon )$-approximation algorithm with $\tilde{O}(n^{5/2+O(\sqrt{\log (1/\epsilon )/\log n})})$ running time of Bernstein and Roditty [SODA 2011] in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of $\tilde{O}(mn/\epsilon )$ and a query time of $O(\log \log n)$. The algorithm has a multiplicative error of $1+\epsilon$ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein [STOC 2013].

A preliminary version was presented at the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS 2013)

References in corpus (3)

• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs

Cited by in corpus (18)

• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Popular conjectures imply strong lower bounds for dynamic problems
• A Survey of Shortest-Path Algorithms
• Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
• Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
• Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
• Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs
• Dynamic Graph Algorithms and Graph Sparsification: New Techniques and Connections
• Input-Dynamic Distributed Algorithms for Communication Networks
• Fully Dynamic Effective Resistances
• Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks
• Approximate Distance Oracles Subject to Multiple Vertex Failures
• Fully Dynamic Spectral Vertex Sparsifiers and Applications
• Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time
• Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs
• A New Deterministic Algorithm for Dynamic Set Cover
• Optimal Dynamic Distributed MIS
• Dynamic Influence Maximization