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 = |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 [JACM81], who provided an algorithm with total update time $O(mn)$ for unweighted undirected graphs; this was later extended to directed weighted graphs [FOCS95, STOC99]. There are conditional lower bounds showing that $O(mn)$ is in fact near-optimal [ESA04, FOCS14, STOC15, STOC20]. 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+{epsilon})$-approximate paths, instead of exact ones [STOC14, ICALP15]. No further progress was made until Probst Gutenberg and Wulff-Nilsen [SODA20] 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})$. 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)$. 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)$. 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.
Download