Logo der Universität Wien

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


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 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(mn^2) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of O(n^{5/2}) and constant query time that has an additive error of two in addition to the 1+? multiplicative error. This beats the previous O(mn) 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+? multiplicative error cannot have an additive error less than 2-?, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick 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 O(n^{5/2+O(1/sqrt{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 O(mn) and a query time of O(log log 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 in his STOC 2013 paper. In order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator. (2) 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.

Grafik Top
Paper in Conference Proceedings or in Workshop Proceedings (Full Paper in Proceedings)
Event Title
FOCS 2013 54th Annual IEEE Symposium on Foundations of Computer Science
Theory and Applications of Algorithms
Theoretische Informatik
Event Location
Berkeley, USA
Event Type
Event Dates
October 27-29, 2013
Series Name
Proceedings 2013 IEEE 54th Annual Symposium on Foundations of Computer Science FOCS 2013
Page Range
pp. 538-547
October 2013
Grafik Top
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna