2026-07-24T11:53:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23381 2025-10-02T12:53:34Z ddc:004 open_access

Induced Disjoint Paths Without an Induced Minor Aboulker, Pierre Bonnet, Édouard Picavet, Timothé Trotignon, Nicolas Induced Disjoint Paths string graphs induced subdivisions induced minors We exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs - which avoids the 1-subdivision of, say, K₅ as an induced minor - Induced 2-Disjoint Paths is NP-complete. So, while k-Disjoint Paths, for a fixed k, is polynomial-time solvable in general graphs, the absence of a graph as an induced minor does not make its induced variant tractable, even for k = 2. This answers a question of Korhonen and Lokshtanov [SODA '24], and complements a polynomial-time algorithm for Induced k-Disjoint Paths in classes of bounded genus by Kobayashi and Kawarabayashi [SODA '09]. In addition to being string graphs, our produced hard instances are subgraphs of a constant power of bounded-degree planar graphs, hence have bounded twin-width and bounded maximum degree. We also leverage our new result to show that there is a fixed subcubic graph H such that deciding if an input graph contains H as an induced subdivision is NP-complete. Until now, all the graphs H for which such a statement was known had a vertex of degree at least 4. This answers a question by Chudnovsky, Seymour, and Trotignon [JCTB '13], and by Le [JGT '19]. Finally we resolve another question of Korhonen and Lokshtanov by exhibiting a subcubic graph H without two adjacent degree-3 vertices and such that deciding if an input n-vertex graph contains H as an induced minor is NP-complete, and unless the Exponential-Time Hypothesis fails, requires time 2^{Ω(√ n)}. This complements an algorithm running in subexponential time 2^{Õ(n^{2/3})} by these authors [SODA '24] under the same technical condition. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Aboulker and Édouard Bonnet and Timothé Picavet and Nicolas Trotignon 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.4 urn:nbn:de:0030-drops-233813 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.4 eng https://creativecommons.org/licenses/by/4.0/legalcode