View article

Dynamic Programming (DP) over tree decompositions is a well-established method to solve problems that are in general NP-hard–efficiently for instances of small treewidth. Experience shows that DP algorithms exhibit a high variance in runtime when using different tree decompositions (TD). In fact, given an instance of the problem at hand, even decompositions of the same width might yield extremely diverging runtimes. We propose a general method that is based on selection of the best decomposition from an available pool of heuristically generated ones. Novel features for tree decomposition are proposed and machine learning techniques are applied to select the most promising decomposition. Extensive experiments in different problem domains show a significant speedup when choosing the tree decomposition according to this concept over simply using an arbitrary one of the same width.