# From Hop Reduction to Sparsification for Negative Length Shortest Paths Preprint · Kent Quanrud, Navid Tajkhorshid - Archive id: arxiv:2511.18253 - Published: 2025-11-23 - arXiv: https://arxiv.org/abs/2511.18253 - Source URL: https://arxiv.org/abs/2511.18253 - PDF: https://arxiv.org/pdf/2511.18253 - Provenance: arxiv ## Abstract The textbook algorithm for real-weighted single-source shortest paths takes $O(mn)$ time on a graph with $m$ edges and $n$ vertices. A recent breakthrough algorithm by \[Fin24\] takes $\\tilde{O}(mn^{8/9})$ randomized time. The running time was subsequently improved to $\\tilde{O}(mn^{4/5})$ \[HJQ25\] and then $\\tilde{O}(mn^{3/4}+m^{4/5}n)$ \[HJQ26\]. We build on the algorithms of \[Fin24; HJQ25; HJQ26\] to obtain faster strongly-polynomial randomized-time algorithms for negative-length shortest paths. An important new technique in this algorithm repurposes previous "hop-reducers" from \[Fin24; HJQ26\] 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 of \[Fin24\] already gives an $\\tilde{O}(mn^{\\sqrt{3}-1})\