Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.42
URN: urn:nbn:de:0030-drops-109867
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10986/
Eiben, Eduard ; Ganian, Robert ; Hamm, Thekla ; Kwon, O-joung
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
| pdf-format: |
|
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: | 20.08.2019 |
