Near-optimal decremental sssp in dense weighted digraphs

Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph G= (V, E, w) undergoing edge deletions and a source vertex r in V; let n= vert V vert, m= vert E vert and W be the aspect ratio of the graph. The goal is to obtain a data structure that maintains shortest paths from r to all vertices in V and can answer distance queries in O(1) time, as well as return the corresponding path P in O(vert P vert) time. This problem was first considered by Even and Shiloach [JACM'81], who provided an algorithm with total update time O(mn) for unweighted undirected graphs; this was later extended to directed weighted graphs [FOCS'95, STOC'99]. There are conditional lower bounds showing that O(mn) is in fact near-optimal [ESA'04, FOCS'14, STOC'15, STOC'20]. In a breakthrough result, Forster et al. showed that total update time min {m{7/6}n{2/3+o(1)}, m{3/4}n{5/4+o(1)} } text{polylog}(W)= mn{0.9+o(1)} text{polylog} (W), is possible if the algorithm is allowed to return (1 + epsilon)-approximate paths, instead of exact ones [STOC'14, ICALP'15]. No further progress was made until Probst Gutenberg and Wulff-Nilsen [SODA'20] provided a new approach for the problem, which yields total time tilde{O}(min {m{2/3}n{4/3} log W, (mn){7/8} log W })= tilde{O}(min {n{8/3} log W, mn{3/4} log W }). Our result builds on this recent approach, but overcomes its limitations by introducing a significantly more powerful abstraction, as well as a different core subroutine. Our new framework yields a decremental (1+ epsilon)-approximate SSSP data structure with total update time tilde{O}(n{2} log{4}W epsilon). Our algorithm is thus near-optimal for dense graphs with polynomial edge-weights. Our framework can also be applied to sparse graphs to obtain total update time tilde{O}(mn{2/3} log{3}W epsilon). Combined, these data structures dominate all previous results. Like all previous o(mn) algorithms that can return a path (not just a distance estimate), our result is randomized and assumes an oblivious adversary. Our framework effectively allows us to reduce SSSP in general graphs to the same problem in directed acyclic graphs (DAGs). We believe that our framework has significant potential to influence future work on directed SSSP, both in the dynamic model and in others.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PublisherIEEE Computer Society
Pages1112-1122
Number of pages11
ISBN (Electronic)9781728196213
DOIs
StatePublished - Nov 2020
Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
Duration: Nov 16 2020Nov 19 2020

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2020-November
ISSN (Print)0272-5428

Conference

Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
Country/TerritoryUnited States
CityVirtual, Durham
Period11/16/2011/19/20

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • dynamic algorithm
  • generalized topological order
  • shortest paths
  • single-source shortest paths

Fingerprint

Dive into the research topics of 'Near-optimal decremental sssp in dense weighted digraphs'. Together they form a unique fingerprint.

Cite this