[Zurück]

E. Eiben, R. Ganian, T. Hamm, O. Kwon:
"Measuring what matters: Ahybrid approach to dynamic programming with treewidth";
Journal of Computer and System Sciences, 121 (2021), S. 57 - 75.

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 forChromatic Number,Hamiltonian Cycle, andMax-Cut.

http://dx.doi.org/10.1016/j.jcss.2021.04.005

https://publik.tuwien.ac.at/files/publik_300279.pdf