{"ID":2841070,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.12714","arxiv_id":"2511.12714","title":"Shortcutting for Negative-Weight Shortest Path","abstract":"Consider the single-source shortest paths problem on a directed graph with real-valued edge weights. We solve this problem in $O(n^{2.5}\\log^{4.5}n)$ time, improving on prior work of Fineman (STOC 2024) and Huang-Jin-Quanrud (SODA 2025, 2026) on dense graphs. Our main technique is an shortcutting procedure that iteratively reduces the number of negative-weight edges along shortest paths by a constant factor.","short_abstract":"Consider the single-source shortest paths problem on a directed graph with real-valued edge weights. We solve this problem in $O(n^{2.5}\\log^{4.5}n)$ time, improving on prior work of Fineman (STOC 2024) and Huang-Jin-Quanrud (SODA 2025, 2026) on dense graphs. Our main technique is an shortcutting procedure that iterati...","url_abs":"https://arxiv.org/abs/2511.12714","url_pdf":"https://arxiv.org/pdf/2511.12714v1","authors":"[\"George Z. Li\",\"Jason Li\",\"Satish Rao\",\"Junkai Zhang\"]","published":"2025-11-16T17:58:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}