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 Õ(n2 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 Õ(mn0.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 Õ(m5/3 log W) total update time. The second one is a randomized algorithm with Õ ((mn1/2 + m7/5) log W) total update time, which improves over both previous results when m = O(n1.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.