2026-06-01T04:22:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8564 2024-03-06T10:41:32Z ddc:004 open_access

Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width Jaffke, Lars Kwon, O-joung Telle, Jan Arne graph width parameters dynamic programming graph classes induced paths induced topological minors We give the first polynomial-time algorithms on graphs of bounded maximum induced matching width (mim-width) for problems that are not locally checkable. In particular, we give n^O(w)-time algorithms on graphs of mim-width at most w, when given a decomposition, for the following problems: Longest Induced Path, Induced Disjoint Paths and H-Induced Topological Minor for fixed H. Our results imply that the following graph classes have polynomial-time algorithms for these three problems: Interval and Bi-Interval graphs, Circular Arc, Per- mutation and Circular Permutation graphs, Convex graphs, k-Trapezoid, Circular k-Trapezoid, k-Polygon, Dilworth-k and Co-k-Degenerate graphs for fixed k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lars Jaffke and O-joung Kwon and Jan Arne Telle 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.21 urn:nbn:de:0030-drops-85643 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.21 eng https://creativecommons.org/licenses/by/3.0/legalcode