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

Please wait, while we are loading the content...

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

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Nanongkai, Danupon Henzinger, Monika Krinninger, Sebastian
Copyright Year	2016
Abstract	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 $\tilde O(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 $\tilde O(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 $\tilde O(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 $\tilde O(n^{5/2+O(\sqrt{\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 $\tilde O(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 $ \tilde O (m n / (\epsilon t))$ and a query time of $ \tilde O (t) $ for every $ t \leq \sqrt{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.
Starting Page	947
Ending Page	1006
Page Count	60
File Format	PDF
ISSN	00975397
DOI	10.1137/140957299
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3 (Special Section on the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013))
Volume Number	45
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2016-06-29
Access Restriction	Subscribed
Subject Keyword	all-pairs shortest paths emulator Nonnumerical algorithms dynamic graph algorithms derandomization Graph algorithms Analysis of algorithms Paths and cycles
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

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

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

Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization (2013)

All-Pairs Almost Shortest Paths

Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs

More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

Fully Dynamic All Pairs All Shortest Paths

Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time

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

Similar Documents

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

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

Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization (2013)

All-Pairs Almost Shortest Paths

Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs

More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

Fully Dynamic All Pairs All Shortest Paths

Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time

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