Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg · Society for Industrial and Applied Mathematics eBooks · 2022
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 Õ(n2) algorithm for this problem, achieving near linear time for very dense graphs. For sparse graphs, Chechik and Zhang [SODA'21] recently presented a deterministic Õ(m5/3) algorithm, and an adaptive randomized algorithm with run-time . This algorithm is remarkable for two reasons: 1) in very spare graphs it reaches the directed hopset barrier of Ω(n3/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 O(m3/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 Õ(m4/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.