Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs

In this paper we show new dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the the problem, that handles updates in O~(n^{4/3} log W/ε) amortized time (where the edge weights are from [1, W]) and explicitly maintains a (1 + ε)-approximate distance matrix. For a fixed ε > 0, this is the first deterministic partially dynamic algorithm for all-pairs shortest paths in directed graphs, whose update time is o(n^2), regardless of the number of edges. To obtain this result, we give a new, very simple deterministic incremental algorithm for the same problem, whose total update time is O~(n^3/ε). This algorithm can be easily adapted to work in the decremental setting within the same time bound. By using our techniques we also show how to improve the state-of-the-art partially dynamic randomized algorithms for all-pairs shortest paths [Baswana et al. STOC’02, Bernstein STOC’13] from Monte Carlo randomized to Las Vegas randomized, without increasing the running time bounds (with respect to the O~() notation).

• Algorithms and Theory