From Hop Reduction to Sparsification for Negative Length Shortest Paths

The textbook algorithm for real-weighted single-source shortest paths takes O(m n) time on a graph with m edges and n vertices. A recent breakthrough algorithm by Fineman [STOC 2024] takes Õ(m n8/9) randomized time. The running time was subsequently improved by Huang, Jin, and Quanrud [SODA 2025, 2026] to Õ(mn4/5) and then Õ(m n3/4 + m4/5 n). We build on these algorithms to obtain faster strongly-polynomial randomized-time algorithms for negative-length shortest paths. An important new technique in this algorithm repurposes previous ”hop-reducers” into ”negative edge sparsifiers”, reducing the number of negative edges by essentially the same factor by which the ”hops” were previously reduced. A simple recursive algorithm based on sparsifying the layered hop reducers already gives an Õ(m n√3−1) < O(mn0.7321) randomized running time, improving all previous bounds uniformly. We also improve the construction of the bootstrapped hop reducers by proposing new sparse shortcut graphs replacing the dense shortcut graphs. Integrating all three of layered sparsification, recursion, and sparse bootstrapping into the algorithm of Huang, Jin, and Quanrud [SODA 2026] gives new upper bounds of O(mn0.7193) randomized time for m ≥ n1.03456 and O((mn)0.8620) randomized time for m ≤ n1.03456. Lastly, concurrent work by Li, Li, Rao, and Zhang [arXiv 2025] obtained an Õ(n2.5) randomized time algorithm for the same problem, and along the way improved the running time of the ”betweenness reduction” step in Fineman’s framework. Dropping in this subroutine as a black box improves the running time of the simple recursive sparsification algorithm to Õ(m n1/√2) ≤ O(mn.70711), and a slightly modified recursive sparsification algorithm runs in O(m n0.69562) randomized time for m ≥ n1.0274 and O((mn)0.850) for m ≤ n1.0274.