Eiben, Eduard ;
Ganian, Robert ;
Hamm, Thekla ;
Kwon, O-joung
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
Abstract
We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i.e., with parts that may not have small treewidth but instead possess other structural properties. Informally, this is achieved by defining a refinement of treewidth which only considers parts of the graph that do not belong to a pre-specified tractable graph class. Our approach allows us to not only generalize existing fixed-parameter algorithms exploiting treewidth, but also fixed-parameter algorithms which use the size of a modulator as their parameter. As the flagship application of our framework, we obtain a parameter that combines treewidth and rank-width to obtain fixed-parameter algorithms for Chromatic Number, Hamiltonian Cycle, and Max-Cut.
BibTeX - Entry
@InProceedings{eiben_et_al:LIPIcs:2019:10986,
author = {Eduard Eiben and Robert Ganian and Thekla Hamm and O-joung Kwon},
title = {{Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {42:1--42:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-117-7},
ISSN = {1868-8969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10986},
URN = {urn:nbn:de:0030-drops-109867},
doi = {10.4230/LIPIcs.MFCS.2019.42},
annote = {Keywords: Parameterized complexity, treewidth, rank-width, fixed-parameter algorithms}
}
|
Keywords: |
|
Parameterized complexity, treewidth, rank-width, fixed-parameter algorithms |
|
Seminar: |
|
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
|
|
Issue date: |
|
2019 |
|
Date of publication: |
|
2019 |
2019
