License:
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.21
URN: urn:nbn:de:0030-drops-85643
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8564/
Jaffke, Lars ;
Kwon, O-joung ;
Telle, Jan Arne
Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width
Abstract
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.
BibTeX - Entry
@InProceedings{jaffke_et_al:LIPIcs:2018:8564,
author = {Lars Jaffke and O-joung Kwon and Jan Arne Telle},
title = {{Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {21:1--21:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8564},
URN = {urn:nbn:de:0030-drops-85643},
doi = {10.4230/LIPIcs.IPEC.2017.21},
annote = {Keywords: graph width parameters, dynamic programming, graph classes, induced paths, induced topological minors}
}
Keywords: |
|
graph width parameters, dynamic programming, graph classes, induced paths, induced topological minors |
Collection: |
|
12th International Symposium on Parameterized and Exact Computation (IPEC 2017) |
Issue Date: |
|
2018 |
Date of publication: |
|
02.03.2018 |