# Faster negative length shortest paths by bootstrapping hop reducers

Preprint · Yufan Huang, Peter Jin, Kent Quanrud

- Archive id: arxiv:2506.00428
- Published: 2025-05-31
- arXiv: https://arxiv.org/abs/2506.00428
- Source URL: https://arxiv.org/abs/2506.00428
- PDF: https://arxiv.org/pdf/2506.00428
- Provenance: arxiv

## Abstract

The textbook algorithm for real-weighted single-source shortest paths takes $O(m n)$ 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}(mn^{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}(mn^{3/4})$ for $m \\geq n^{5/4}$, and $\\tilde{O}(m^{4/5} n)$ for $m \\leq 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.