The Directed Disjoint Paths Problem with Congestion
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_ | 1866909691313913856 |
|---|---|
| author | Bentert, Matthias Cavallaro, Dario Heindl, Amelie Kawarabayashi, Ken-ichi Kreutzer, Stephan Schröder, Johannes |
| author_facet | Bentert, Matthias Cavallaro, Dario Heindl, Amelie Kawarabayashi, Ken-ichi Kreutzer, Stephan Schröder, Johannes |
| contents | The classic result by Fortune, Hopcroft, and Wyllie [TCS~'80] states that the directed disjoint paths problem is NP-complete even for two pairs of terminals. Extending this well-known result, we show that the directed disjoint paths problem is NP-complete for any constant congestion $c \geq 1$ and~$k \geq 3c-1$ pairs of terminals. This refutes a conjecture by Giannopoulou et al. [SODA~'22], which says that the directed disjoint paths problem with congestion two is polynomial-time solvable for any constant number $k$ of terminal pairs. We then consider the cases that are not covered by this hardness result. The first nontrivial case is $c=2$ and $k = 3$. Our second main result is to show that this case is polynomial-time solvable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12096 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Directed Disjoint Paths Problem with Congestion Bentert, Matthias Cavallaro, Dario Heindl, Amelie Kawarabayashi, Ken-ichi Kreutzer, Stephan Schröder, Johannes Discrete Mathematics Combinatorics 05C83, 05C85, 05C10, 05C75, 68R10 F.2.0; G.2.2 The classic result by Fortune, Hopcroft, and Wyllie [TCS~'80] states that the directed disjoint paths problem is NP-complete even for two pairs of terminals. Extending this well-known result, we show that the directed disjoint paths problem is NP-complete for any constant congestion $c \geq 1$ and~$k \geq 3c-1$ pairs of terminals. This refutes a conjecture by Giannopoulou et al. [SODA~'22], which says that the directed disjoint paths problem with congestion two is polynomial-time solvable for any constant number $k$ of terminal pairs. We then consider the cases that are not covered by this hardness result. The first nontrivial case is $c=2$ and $k = 3$. Our second main result is to show that this case is polynomial-time solvable. |
| title | The Directed Disjoint Paths Problem with Congestion |
| topic | Discrete Mathematics Combinatorics 05C83, 05C85, 05C10, 05C75, 68R10 F.2.0; G.2.2 |
| url | https://arxiv.org/abs/2507.12096 |