TY - GEN

T1 - Near-optimal decremental sssp in dense weighted digraphs

AU - Bernstein, Aaron

AU - Gutenberg, Maximilian Probst

AU - Wulff-Nilsen, Christian

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - dynamic algorithm

KW - generalized topological order

KW - shortest paths

KW - single-source shortest paths

UR - http://www.scopus.com/inward/record.url?scp=85098379480&partnerID=8YFLogxK

U2 - 10.1109/FOCS46700.2020.00107

DO - 10.1109/FOCS46700.2020.00107

M3 - Article in proceedings

AN - SCOPUS:85098379480

SP - 1112

EP - 1122

BT - Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020

PB - IEEE

T2 - 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020

Y2 - 16 November 2020 through 19 November 2020

ER -