{"ID":2850073,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.22721","arxiv_id":"2510.22721","title":"Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions","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).","short_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 decomp...","url_abs":"https://arxiv.org/abs/2510.22721","url_pdf":"https://arxiv.org/pdf/2510.22721v1","authors":"[\"Jason Li\",\"Connor Mowry\",\"Satish Rao\"]","published":"2025-10-26T15:38:16Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}