Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.18253 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909930299064320 |
|---|---|
| author | Quanrud, Kent Tajkhorshid, Navid |
| author_facet | Quanrud, Kent Tajkhorshid, Navid |
| contents | 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})<O(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<n^{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}})<O(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<n^{1.0274}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_18253 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | From Hop Reduction to Sparsification for Negative Length Shortest Paths Quanrud, Kent Tajkhorshid, Navid Data Structures and Algorithms 05C85 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})<O(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<n^{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}})<O(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<n^{1.0274}$. |
| title | From Hop Reduction to Sparsification for Negative Length Shortest Paths |
| topic | Data Structures and Algorithms 05C85 |
| url | https://arxiv.org/abs/2511.18253 |