{"ID":2837873,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.18253","arxiv_id":"2511.18253","title":"From Hop Reduction to Sparsification for Negative Length Shortest Paths","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})\u003cO(mn^{.7321})$ randomized running time, improving [HJQ26] uniformly. We also improve the construction of the bootstrapped hop reducers in [HJQ26] by proposing new sparse shortcut graphs replacing the dense shortcut graphs in [HJQ26]. Integrating all three of layered sparsification, recursion, and sparse bootstrapping into the algorithm of [HJQ26] gives new upper bounds of $O(mn^{.7193})$ randomized time for $m\\geq n^{1.03456}$ and $O((mn)^{.8620})$ randomized time for $m\u003cn^{1.03456}$. Lastly, concurrent work by [LLRZ25] obtained an $\\tilde{O}(n^{2.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 $\\tilde{O}(mn^{1/\\sqrt{2}})\u003cO(mn^{.70711})$, and a slightly modified recursive sparsification algorithm runs in $O(mn^{.69562})$ randomized time for $m\\geq n^{1.0274}$ and $O((mn)^{.85})$ for $m\u003cn^{1.0274}$.","short_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^...","url_abs":"https://arxiv.org/abs/2511.18253","url_pdf":"https://arxiv.org/pdf/2511.18253v2","authors":"[\"Kent Quanrud\",\"Navid Tajkhorshid\"]","published":"2025-11-23T02:43:51Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}