Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization
Henzinger MH, Krinninger S, Nanongkai D. 2016. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 45(3), 947β1006.
Download (ext.)
https://arxiv.org/abs/1308.0776
[Preprint]
Journal Article
| 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 π-node π-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of πΜ (ππ/π) 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 π(ππ2) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of πΜ (π5/2/π) and constant query time that has an additive error of 2 in addition to the 1+π multiplicative error. This beats the previous πΜ (ππ/π) time when π=Ξ©(π3/2). Note that the additive error is unavoidable since, even in the static case, an π(π3βπΏ)-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 [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+π)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3+π)-approximation algorithm with πΜ (π5/2+π(log(1/π)/logπβ)) 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 πΜ (ππ/π) and a query time of π(loglogπ). 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 [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+π)-approximation with an amortized update time of πΜ (ππ/(ππ‘)) and a query time of πΜ (π‘) for every π‘β€πβ. 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.
Publishing Year
Date Published
2016-05-01
Journal Title
SIAM Journal on Computing
Publisher
Society for Industrial & Applied Mathematics
Volume
45
Issue
3
Page
947-1006
ISSN
eISSN
IST-REx-ID
Cite this
Henzinger MH, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 2016;45(3):947-1006. doi:10.1137/140957299
Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2016). Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/140957299
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. βDynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.β SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2016. https://doi.org/10.1137/140957299.
M. H. Henzinger, S. Krinninger, and D. Nanongkai, βDynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization,β SIAM Journal on Computing, vol. 45, no. 3. Society for Industrial & Applied Mathematics, pp. 947β1006, 2016.
Henzinger MH, Krinninger S, Nanongkai D. 2016. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 45(3), 947β1006.
Henzinger, Monika H., et al. βDynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.β SIAM Journal on Computing, vol. 45, no. 3, Society for Industrial & Applied Mathematics, 2016, pp. 947β1006, doi:10.1137/140957299.
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