What type of study is this?

This is a Quantitative Study study.

October 15, 2025Open Access

The Directed Disjoint Paths Problem with Congestion

Key Points

This research confirms that the directed disjoint paths problem is NP-complete for any constant congestion and multiple terminal pairs.
It refutes a previous conjecture that claimed polynomial-time solvability for congestion two with multiple terminal pairs.
The study identifies a polynomial-time solvable case for congestion two and three terminal pairs, adding nuance to the understanding of the problem.
These findings indicate that while certain configurations are incredibly complex, specific cases still offer feasible solutions.

Abstract

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 1 and~k 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.

Read Full Paperexternally

KI fragen

Bookmark

View Full Paper

Cite This Study

Bentert et al. (Wed,) studied this question.

synapsesocial.com/papers/68ef858cc6a308ba06355514 https://doi.org/https://doi.org/10.48550/arxiv.2507.12096

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

KI fragen

Bookmark

View Full Paper