Bernstein, Aaron
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs
Abstract
In this paper we consider the decremental singlesource shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest distances between s and all other nodes in G under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem in unweighted graphs with only O(mn) total update time over all edge deletions. Their classic algorithm was the state of the art for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed.
The first improvement over the EvenShiloach algorithm was given by Bernstein and Roditty [SODA 2011], who for the case of an unweighted and undirected graph presented a (1+epsilon)approximate algorithm with constant query time and a total update time of O(n^{2+o(1)}). This work triggered a series of new results, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a (1+epsilon)approximate algorithm for undirected weighted graphs whose total update time is near linear: O(m^{1+o(1)} log(W)), where W is the ratio of the heaviest to the lightest edge weight in the graph. In this paper they posed as a major open problem the question of derandomizing their result.
Until very recently, all known improvements over the EvenShiloach algorithm were randomized and required the assumption of a nonadaptive adversary. In STOC 2016, Bernstein and Chechik showed the first deterministic
algorithm to go beyond O(mn) total update time: the algorithm is also (1+\epsilon)approximate, and has total update time \tilde{O}(n^2). In SODA 2017, the same authors presented an algorithm with total update time \tilde{O}(mn^{3/4}). However, both algorithms are restricted to undirected, unweighted graphs. We present the first deterministic algorithm for weighted undirected graphs to go beyond the O(mn) bound. The total update time is \tilde{O}(n^2 \log(W)).
BibTeX  Entry
@InProceedings{bernstein:LIPIcs:2017:7401,
author = {Aaron Bernstein},
title = {{Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {44:144:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7401},
URN = {urn:nbn:de:0030drops74013},
doi = {10.4230/LIPIcs.ICALP.2017.44},
annote = {Keywords: Shortest Paths, Dynamic Algorithms, Deterministic, Weighted Graph}
}
07.07.2017
Keywords: 

Shortest Paths, Dynamic Algorithms, Deterministic, Weighted Graph 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 