Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

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…