Faster negative length shortest paths by bootstrapping hop reducers

Abstract

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 $\tilde{O}(m{n}^{8/9})$ randomized time. The running time was subsequently improved to $\tilde{O}(m{n}^{4/5})$ [HJQ25]. We build on [Fin24; HJQ25] to obtain an $\tilde{O}(m{n}^{3/4}+m^{4/5}n)$ randomized running time. (Equivalently, $\tilde{O}(m{n}^{3/4})$ for $m\ge n^{5/4}$, and $\tilde{O}(m^{4/5}n)$ for $m\le 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.

SODA 2026. Figures added