{"id":"arxiv:2511.12714","kind":"preprint","title":"Shortcutting for Negative-Weight Shortest Path","authors":["George Z. Li","Jason Li","Satish Rao","Junkai Zhang"],"author_count":4,"year":2025,"published":"2025-11-16","venue":null,"cited_by":0,"doi":null,"arxiv_id":"2511.12714","nct_id":null,"source_url":"https://arxiv.org/abs/2511.12714","archive_url":"https://space-kitty.com/papers/arxiv:2511.12714","updated":"2025-11-16","pmid":null,"pmcid":null,"openalex_id":"W4416614274","pdf_url":"https://arxiv.org/pdf/2511.12714","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.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[{"slug":"algorithms-complexity","name":"Algorithms & Complexity Breakthroughs","domain_slug":"math-cs"}],"cited_in_dossiers":[]}