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: https://drops.dagstuhl.de/opus/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
| pdf-format: |
|
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 | |
| Seminar: | 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) | |
| Issue date: | 2018 | |
| Date of publication: | 02.03.2018 |
