Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth

EIBEN, Eduard, Robert GANIAN, Thekla HAMM and O-joung KWON. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. Online. In Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen. 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Nemecko: Dagstuhl, 2019, p. 1-15. ISBN 978-3-95977-117-7. Available from: https://dx.doi.org/10.4230/LIPIcs.MFCS.2019.42.

Basic information

• Original name: Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
• Authors: EIBEN, Eduard (703 Slovakia), Robert GANIAN (203 Czech Republic, guarantor, belonging to the institution), Thekla HAMM (276 Germany) and O-joung KWON (410 Republic of Korea).
• Edition: Nemecko, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), p. 1-15, 15 pp. 2019.
• Publisher: Dagstuhl

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: electronic version available online
• WWW: URL
• RIV identification code: RIV/00216224:14330/19:00113726
• Organization unit: Faculty of Informatics
• ISBN: 978-3-95977-117-7
• ISSN: 1868-8969
• Doi: http://dx.doi.org/10.4230/LIPIcs.MFCS.2019.42
• Keywords in English: Parameterized Complexity
• Tags: core_A, firank_A

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.