2026-07-24T05:46:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23467 2025-10-02T12:55:59Z ddc:004 open_access

Revisiting Directed Disjoint Paths on Tournaments (And Relatives) de C. M. Gomes, Guilherme Lopes, Raul Sau, Ignasi directed graphs tournaments semicomplete digraphs directed disjoint paths congestion parameterized complexity directed pathwidth In the Directed Disjoint Paths problem (k-DDP), we are given a digraph and k pairs of terminals, and the goal is to find k pairwise vertex-disjoint paths connecting each pair of terminals. Bang-Jensen and Thomassen [SIAM J. Discrete Math. 1992] claimed that k-DDP is NP-complete on tournaments, and this result triggered a very active line of research about the complexity of the problem on tournaments and natural superclasses. We identify a flaw in their proof, which has been acknowledged by the authors, and provide a new NP-completeness proof. From an algorithmic point of view, Fomin and Pilipczuk [J. Comb. Theory B 2019] provided an FPT algorithm for the edge-disjoint version of the problem on semicomplete digraphs, and showed that their technique cannot work for the vertex-disjoint version. We overcome this obstacle by showing that the version of k-DDP where we allow congestion c on the vertices is FPT on semicomplete digraphs provided that c is greater than k/2. This is based on a quite elaborate irrelevant vertex argument inspired by the edge-disjoint version, and we show that our choice of c is best possible for this technique, with a counterexample with no irrelevant vertices when c ≤ k/2. We also prove that k-DDP on digraphs that can be partitioned into h semicomplete digraphs is W[1]-hard parameterized by k+h, which shows that the XP algorithm presented by Chudnovsky, Scott, and Seymour [J. Comb. Theory B 2019] is essentially optimal. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guilherme de C. M. Gomes and Raul Lopes and Ignasi Sau 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.90 urn:nbn:de:0030-drops-234678 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.90 eng https://creativecommons.org/licenses/by/4.0/legalcode