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

arXiv: https://arxiv.org/abs/1308.0776 · HTML: https://mlsanity.com/paper/1308.0776/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2013.

## Built on by (most cited first, 1 of 1)

- [Incremental Approximate Single-Source Shortest Paths with Predictions](https://mlsanity.com/paper/2502.08125/) (2025)

## Abstract (arXiv)

We study dynamic (1+ε)-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/ε) 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(mn2) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of tilde O(n5/2/ε) and constant query time that has an additive error of 2 in addition to the 1+ε multiplicative error. This beats the previous tilde O(mn/ε) time when m=Omega(n3/2). Note that the additive error is unavoidable since, even in the static case, an O(n3-δ)-time (a so-called truly subcubic) combinatorial algorithm with 1+ε multiplicative error cannot have an additive error less than 2-ε, 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+ε)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3+ε)-approximation algorithm with tilde O(n^5/2+O(√log(1/ε)/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/ε) and a query time of O(loglog n). The algorithm has a multiplicative error of 1+ε and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein [STOC 2013].