Informace o publikaci
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
| Autoři | |
|---|---|
| Rok publikování | 2019 |
| Druh | Článek ve sborníku |
| Konference | 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://drops.dagstuhl.de/opus/volltexte/2019/10986/ |
| Doi | http://dx.doi.org/10.4230/LIPIcs.MFCS.2019.42 |
| Klíčová slova | Parameterized Complexity |
| Popis | 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. |