---
_id: '11856'
abstract:
- lang: eng
text: '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.'
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: 'Henzinger MH, 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'
apa: 'Henzinger, M. H., 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'
chicago: 'Henzinger, Monika H, 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.'
ieee: 'M. H. 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.'
ista: 'Henzinger MH, 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.'
mla: 'Henzinger, Monika H., 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.'
short: M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 54th Annual Symposium on
Foundations of Computer Science, Institute of Electrical and Electronics Engineers,
2013, pp. 538–547.
conference:
end_date: 2013-10-29
location: Berkeley, CA, United States
name: 'FOCS: Symposium on Foundations of Computer Science'
start_date: 2013-10-26
date_created: 2022-08-16T08:22:37Z
date_published: 2013-10-01T00:00:00Z
date_updated: 2023-02-17T09:56:04Z
day: '01'
doi: 10.1109/focs.2013.64
extern: '1'
external_id:
arxiv:
- '1308.0776'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1308.0776
month: '10'
oa: 1
oa_version: Preprint
page: 538-547
publication: 54th Annual Symposium on Foundations of Computer Science
publication_identifier:
eisbn:
- 978-0-7695-5135-7
issn:
- 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and
derandomization'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...