Incremental Single Source Shortest Paths in Sparse Digraphs

Given a directed graph G = ( V, E, ω ) with positive integer edge weights that undergoes a sequence of edge insertions, we are interested in maintaining approximate single-source shortest paths in the incremental graph G. In a very recent paper, [Gutenberg et al. , 2020] proposed a deterministic algorithm for this problem with Õ(n 2 log W ) total update time, where n = |V| and W denotes the maximum edge weight. When the underlying graph is super dense, namely, the total number of insertions m is, their upper bound is essentially optimal. For sparse graphs, the only known result is due to [Henzinger et al. , 2014], whose algorithm is randomized and works in Õ(mn 0. 9 log W ) total update time under the assumption of oblivious non-adaptive adversary. In this work, we provide two algorithms for this problem when the graph is sparse. The first one is a simple deterministic algorithm with Õ ( m 5/3 log W ) total update time. The second one is a randomized algorithm with Õ (( mn 1/2 + m 7/5 ) log W ) total update time, which improves over both previous results when m = O ( n 1. 42 ); moreover, this randomized algorithm plays against adaptive adversaries. Our algorithms are the first to break the O ( mn ) bound with adaptive adversaries for sparse graphs.

Authors

• Shiri Chechik
• Tianyi Zhang 0008

Keywords

No keywords are indexed for this paper.