Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier

Given a directed, weighted graph G = (V, E) undergoing edge insertions, the incremental single-source shortest paths (SSSP) problem asks for the maintenance of approximate distances from a dedicated source s while optimizing the total time required to process the insertion sequence of m edges.

Recently, Gutenberg, Williams and Wein [STOC'20] introduced a deterministic Õ(n 2 ) algorithm for this problem, achieving near linear time for very dense graphs. For sparse graphs, Chechik and Zhang [SODA'21] recently presented a deterministic Õ(m 5/3 ) algorithm, and an adaptive randomized algorithm with run-time Õ(m √ n + m 7/5 ). This algorithm is remarkable for two reasons: 1) in very spare graphs it reaches the directed hopset barrier of Ω(n 3/2 ) that applied to all previous approaches for partially-dynamic SSSP [STOC'14, SODA'20, FOCS'20] and 2) it does not resort to a directed hopset technique itself.

In this article we introduce propagation synchronization, a new technique for controlling the error build-up on paths throughout batches of insertions. This leads us to a significant improvement of the approach in [SODA'21] yielding a deterministic Õ(m 3/2 ) algorithm for the problem. By a very careful combination of our new technique with the sampling approach from [SODA'21], we further obtain an adaptive randomized algorithm with total update time Õ(m 4/3 ). This is the first partially-dynamic SSSP algorithm in sparse graphs to bypass the notorious directed hopset barrier which is often seen as the fundamental challenge towards achieving truly near-linear time algorithms.

The research leading to these results has received funding from grant no. 200021 204787 of the Swiss National Science Foundation.