De Castro Mendes Gomes GuilhermeTeixeira Lopes, Raul WayneRaul WayneTeixeira LopesSau, IgnasiIgnasiSau2025-07-162025-07-162025-06-3052nd International Colloquium on Automata, Languages, and Programming, ICALP 20259783959773720https://hdl.handle.net/11420/56236In 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.enhttps://creativecommons.org/licenses/by/4.0/congestion | directed disjoint paths | directed graphs | directed pathwidth | parameterized complexity | semicomplete digraphs | tournamentsComputer Science, Information and General Works::004: Computer SciencesNatural Sciences and Mathematics::519: Applied Mathematics, ProbabilitiesConference Paperhttps://doi.org/10.15480/882.1539710.4230/LIPIcs.ICALP.2025.9010.15480/882.15397Conference Paper