Near-optimal decremental sssp in dense weighted digraphs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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
Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PublisherIEEE
Publication date2020
Pages1112-1122
Article number9317923
ISBN (Electronic)9781728196213
DOIs
Publication statusPublished - 2020
Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
Duration: 16 Nov 202019 Nov 2020

Conference

Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
LandUnited States
ByVirtual, Durham
Periode16/11/202019/11/2020
SponsorIEEE Computer Society Technical Committee on Mathematical Foundations of Computing

    Research areas

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

ID: 258706807