Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915612111929344 |
|---|---|
| author | Haeupler, Bernhard Jiang, Yonggang Saranurak, Thatchaphol |
| author_facet | Haeupler, Bernhard Jiang, Yonggang Saranurak, Thatchaphol |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_08551 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers Haeupler, Bernhard Jiang, Yonggang Saranurak, Thatchaphol Data Structures and Algorithms 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. |
| title | Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.08551 |