DYNAMIC APPROXIMATE ALL-PAIRS SHORTEST PATHS: BREAKING THE O(mn) BARRIER AND DERANDOMIZATION

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 (O) over tilde (mn/epsilon) and constant query time by Roditty and Zwick [SIAM J. Comput., 41 (2012), pp. 670-683]. The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach [J. ACM, 28 (1981), pp. 1-4]; it has a total update time of O(mn(2)) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of (O) over tilde (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 (O) over tilde (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 [D. Dor, S. Halrepin, and U. Zwick, SIAM J. Comput., 29 (2000), pp. 1740-1759] and many other long-standing problems [V. Vassilevska Williams and R. Williams, Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 645-654]. 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 (O) over tilde (n(5/2+O(root log(1/epsilon)/log n))) running time of Bernstein and Roditty [Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 1355-1365] in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of (O) over tilde (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 in [Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 2013, pp. 725-734]. The deterministic algorithm can be turned into a deterministic fully dynamic (1+ epsilon)-approximation with an amortized update time of (O) over tilde (mn/(epsilon t)) and a query time of (O) over tilde (t) for every t <= root n. In order to achieve our results, we introduce two new techniques: (i) A monotone Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called a locally persevering emulator. (ii) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.