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

Eduard Eiben, Robert Ganian, Thekla Hamm +1

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 ot…