The Directed Disjoint Paths Problem with Congestion

2025/07/16 by Bentert, Matthias, Cavallaro, Dario, Heindl, Amelie +3
#05C10 #05C75 #05C83 #05C85 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #F.2.0 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.2507.12096

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.

Citations

• Constant congestion linkages in polynomially strong digraphs in polynomial time
• Cycles of Well-Linked Sets I: an Elementary Bound for Directed Cycle Packing
• Minor Containment and Disjoint Paths in almost-linear time
• New Menger-like dualities in digraphs and applications to half-integral linkages
• Adapting the Directed Grid Theorem into an FPT Algorithm
• Half-integral linkages in highly connected directed graphs
• Routing with Congestion in Acyclic Digraphs
• The Directed Grid Theorem
• The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter\n tractable

Related

• Routing with Congestion in Acyclic Digraphs
• Revisiting Directed Disjoint Paths on tournaments (and relatives)
• A Polynomial Time Algorithm for the k-Disjoint Shortest Paths Problem
• Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
• Disjoint Shortest Paths with Congestion on DAGs