# Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions

Preprint · Jason Li, Connor Mowry, Satish Rao

- Archive id: arxiv:2510.22721
- Published: 2025-10-26
- arXiv: https://arxiv.org/abs/2510.22721
- Source URL: https://arxiv.org/abs/2510.22721
- PDF: https://arxiv.org/pdf/2510.22721
- Provenance: arxiv

## Abstract

We present a faster algorithm for low-diameter decompositions on directed graphs, matching the $O(\\log n\\log\\log n)$ loss factor from Bringmann, Fischer, Haeupler, and Latypov (ICALP 2025) and improving the running time to $O((m+n\\log\\log n)\\log n\\log\\log n)$ in expectation. We then apply our faster low-diameter decomposition to obtain an algorithm for negative-weight single source shortest paths on integer-weighted graphs in $O((m+n\\log\\log n)\\log(nW)\\log n\\log\\log n)$ time, a nearly log-factor improvement over the algorithm of Bringmann, Cassis, and Fischer (FOCS 2023).

_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.