Near-Optimal Decremental SSSP in Dense Weighted Digraphs

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 total update time minm 7/6 n 2/3+o(1) , m 3/4 n 5/4+o(1) polylog(W ) = mn 0.9+o(1) polylogW is possible 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

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/3 log 3 W/ǫ). 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.

The key contribution of our paper is a general technique for converting algorithms on directed acyclic graphs (DAGs) into algorithms on general graphs. Earlier techniques in [Ber17; GW20a] lead to two simple algorithms for DAGs with total update times Õ(n 2 ) and Õ(mn 2/3 ); our conversion then extends these bounds to general graphs. We first introduce the concept approximate topological order (AT O), which loosely speaking imposes a DAG-like structure on any graph. We then show that an AT O always exists and can be maintained efficiently.

At a high-level, the conversion is as follows. Let A DAG be a decremental SSSP algorithm for DAGs and let T (A DAG ) be the total update time. The first (easier) step is to convert A DAG to an algorithm A * DAG that works on any graph with an AT O and has total update time T (A * DAG ) ∼ T (A DAG ). The second (harder) step is to build an algorithm A AT O that maintains an AT O in G by recursively applying A * DAG as a subroutine: the basic idea is that an AT O of better "quality" can be built by using A * DAG to maintain shortest paths in an AT O of worse quality. Using this layered approach, we can achieve T (A AT O ) ∼ T (A * DAG ) ∼ T (A DAG ), and combining A AT O with A * DAG gives an algorithm for general graphs. Neither the step from A DAG to A * DAG nor the step from A * DAG to A AT O are black-box, but the techniques are quite modular and flexible, as evidenced by the fact that we were able to apply this conversion to both of the state-of-the-art algorithms for DAGs. We believe our conversion has strong potential to influence future work on directed shortest paths, in both the dynamic model and in others, by allowing researchers to focus on the simpler case of DAGs.

We let a graph H refer to a weighted, directed graph with vertex set denoted by V (H), edge set E(H) and weight function w H : E(H) → [1, W ] ∪ ∞ 2 . We say that H is a decremental graph if it is undergoing a sequence of edge deletions and edge weight increases (also referred to as updates), and refer to version t of H, or H at stage t as the graph H obtained after the first t updates have been applied. In this article, we denote the (decremental) input graph by G = (V, E, w) with n = |V | and m = |E| (where m refers to the number of edges of G at stage 0). In all subsequent definitions, we often use a subscript to indicate which graph we refer to, however, when we refer to G, we often omit the subscript.