Near-Optimal Decremental SSSP in Dense Weighted Digraphs
share
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 ∈ V; let n = |V|, m = |E| 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(|P|) 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 it is possible to achieve total update time mn^0.9+o(1)log W if the algorithm is allowed to return (1+ϵ)-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 Õ(minm^2/3n^4/3log W, (mn)^7/8log 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+ϵ)-approximate SSSP data structure with total update time Õ(n^2 log^4 W). 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 Õ(mn^2/3log^3 W). Our main technique allows us to convert SSSP algorithms for DAGs to ones for general graphs, which we believe has significant potential to influence future work.
READ FULL TEXT