{"id":"arxiv:2511.08551","kind":"preprint","title":"Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers","authors":["Bernhard Haeupler","Yonggang Jiang","Thatchaphol Saranurak"],"author_count":3,"year":2025,"published":"2025-11-11","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2511.08551","nct_id":null,"source_url":"https://arxiv.org/abs/2511.08551","archive_url":"https://space-kitty.com/papers/arxiv:2511.08551","updated":"2025-11-11","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2511.08551","abstract":"We present the first deterministic nearly-linear time algorithm for single-source shortest paths with negative edge weights on directed graphs: given a directed graph $G$ with $n$ vertices, $m$ edges whose weights are integer in $\\{-W,\\dots,W\\}$, our algorithm either computes all distances from a source $s$ or reports a negative cycle in time $\\tilde{O}(m)\\cdot \\log(nW)$ time. All known near-linear time algorithms for this problem have been inherently randomized, as they crucially rely on low-diameter decompositions. To overcome this barrier, we introduce a new structural primitive for directed graphs called the path cover. This plays a role analogous to neighborhood covers in undirected graphs, which have long been central to derandomizing algorithms that use low-diameter decomposition in the undirected setting. We believe that path covers will serve as a fundamental tool for the design of future deterministic algorithms on directed graphs.","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":[],"cited_in_dossiers":[]}