Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization
Henzinger M, Krinninger S, Nanongkai D. 2013. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. 54th Annual Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science, 538–547.
Download (ext.)
https://arxiv.org/abs/1308.0776
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Krinninger, Sebastian;
Nanongkai, Danupon
Abstract
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 Ȏ(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 Ȏ(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 Ȏ(mn) time when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in the static case, an O(n 3-δ )-time (a so-called truly sub cubic) 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 Ȏ(n 5/2+O(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 Ȏ(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.
Publishing Year
Date Published
2013-10-01
Proceedings Title
54th Annual Symposium on Foundations of Computer Science
Publisher
Institute of Electrical and Electronics Engineers
Page
538-547
Conference
FOCS: Symposium on Foundations of Computer Science
Conference Location
Berkeley, CA, United States
Conference Date
2013-10-26 – 2013-10-29
ISSN
IST-REx-ID
Cite this
Henzinger M, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. In: 54th Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2013:538-547. doi:10.1109/focs.2013.64
Henzinger, M., Krinninger, S., & Nanongkai, D. (2013). Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. In 54th Annual Symposium on Foundations of Computer Science (pp. 538–547). Berkeley, CA, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/focs.2013.64
Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” In 54th Annual Symposium on Foundations of Computer Science, 538–47. Institute of Electrical and Electronics Engineers, 2013. https://doi.org/10.1109/focs.2013.64.
M. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization,” in 54th Annual Symposium on Foundations of Computer Science, Berkeley, CA, United States, 2013, pp. 538–547.
Henzinger M, Krinninger S, Nanongkai D. 2013. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. 54th Annual Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science, 538–547.
Henzinger, Monika, et al. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” 54th Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2013, pp. 538–47, doi:10.1109/focs.2013.64.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1308.0776