Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary

Given a dynamic digraph G = (V, E) undergoing edge deletions and given s ϵ V and constant ϵ with 0 < ϵ ≤ 1, we consider the problem of maintaining (1+ϵ)-approximate shortest path distances from s to all vertices in G over the sequence of deletions. Even and Shiloach (J. ACM’81) give a deterministic data structure for the exact version of the problem in unweighted graphs with total update time O(mn). Henzinger et al. (STOC’14, ICALP’15) give a Monte Carlo data structure for the approximate version with an improved total update time bound of O(mn0.9+°(1) log W) with better bounds for sufficiently dense and sufficiently sparse graphs; here W is the ratio between the largest and smallest edge weight. A drawback of their data structure and in fact of all previous randomized data structures is that they only work against an oblivious adversary, meaning that the sequence of deletions needs to be fixed in advance. This severely limits its application as a black box inside algorithms. We present the following (1 + ϵ)-approximate data structures: the first data structure is Las Vegas and works against an adaptive adversary; it has total expected update time Õ(m2/3n4/3)1 for unweighted graphs and Õ(m3/4n5/4 log W) for weighted graphs, the second data structure is Las Vegas and assumes an oblivious adversary; it has total expected update time for unweighted graphs and Õ(m2/3n4/3 log W) for weighted graphs, the third data structure is Monte Carlo and is correct w.h.p. against an oblivious adversary; it has total expected update time Õ((mn)7/8 log W) = Õ(mn3/4 log W). Each of our data structures can report the length of a (1 + ϵ)-approximate shortest path from s to any query vertex in constant time at any point during the sequence of updates; if the adversary is oblivious, a query can be extended to also report such a path in time proportional to its length. Our update times are faster than those of Henzinger et al. for all graph densities. For instance, when m = Θ(n2), our second result improves their bound from O(n2+3/4+o(1) log W) to Õ(n2+1/2) in the unweighted setting and to Õ(n2+2/3 log W) in the weighted setting. When m = Θ(n), our third result gives an improvement from O(n1+5/6+o(1) log W) to Õ(n1+3/4 log W). Furthermore, our first data structure is the first to improve on the O(mn) bound of Even and Shiloach for all but the sparsest graphs while still working against an adaptive adversary and works even in weighted graphs; this answers an open problem by Henzinger et al.