2026-08-16T11:28:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25134 2025-12-15T07:48:49Z ddc:004 open_access

Directed Disjoint Paths Remains W[1]-Hard on Acyclic Digraphs Without Large Grid Minors Kawarabayashi, Ken-ichi Lorenz, Nicola Garlet Milani, Marcelo Stegemann, Jacob digraphs parameterized complexity disjoint paths butterfly minors immersions ear anonymity In the Vertex-Disjoint-Paths-With-Congestion problem, the input consists of a digraph D, an integer c and k pairs of vertices (s_i, t_i), and the task is to find a set of paths connecting each s_i to its corresponding t_i, whereas each vertex of D appears in at most c many paths. The case where c = 1 is known to be NP-complete even if k = 2 [Fortune, Hopcroft and Wyllie, 1980] on general digraphs and is W[1]-hard with respect to k (excluding the possibility of an f(k)n^O(1)-time algorithm under standard assumptions) on acyclic digraphs [Slivkins, 2010]. The proof of [Slivkins, 2010] can also be adapted to show W[1]-hardness with respect to k for every congestion c ≥ 1. We strengthen the existing hardness result by showing that the problem remains W[1]-hard for every congestion c ≥ 1 even if: (1) the input digraph D is acyclic, (2) D does not contain an acyclic (5, 5)-grid as a butterfly minor, (3) D does not contain an acyclic tournament on 9 vertices as a butterfly minor, and (4) D has ear-anonymity at most 5. Further, we also show that the edge-congestion variant of the problem remains W[1]-hard for every congestion c ≥ 1 even if: (1) the input digraph D is acyclic, (2) D has maximum undirected degree 3, (3) D does not contain an acyclic (7, 7)-wall as a weak immersion and (4) D has ear-anonymity at most 5. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ken-ichi Kawarabayashi and Nicola Lorenz and Marcelo Garlet Milani and Jacob Stegemann 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.2 urn:nbn:de:0030-drops-251347 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.2 eng https://creativecommons.org/licenses/by/4.0/legalcode