Faster negative length shortest paths by bootstrapping hop reducers

The textbook algorithm for real-weighted single-source shortest paths takes O(mn) time on a graph with m edges and n vertices. The breakthrough algorithm by Fineman [Fin24] takes Õ mn 8/9 randomized time. The running time was subsequently improved to Õ mn 4/5 [HJQ25].

We build on [Fin24; HJQ25] to obtain an Õ mn 3/4 + m 4/5 n randomized running time. (Equivalently, Õ mn 3/4 for m ≥ n 5/4 , and Õ m 4/5 n for m ≤ n 5/4 .) The main new technique replaces the hop-reducing auxiliary graph from [Fin24] with a bootstrapping process where constant-hop reducers for small subgraphs of the input graph are iteratively amplified and expanded until the desired polynomial-hop reduction is achieved over the entire graph.

huan1754,