Tailored tree decompositions for efficient problem solving

Abstract

Decompositions of graphs and hypergraphs play a central role in the field of parameterized complexity theory. Tree decompositions are a prominent concept in this context since - given that instances enjoy certain structural properties - dynamic programming on tree decompositions allows to solve many computational problems efficiently although they are intractable in the general case. This is because tree decompositions are the basis for many fixed-parameter tractable algorithms for solving NP-hard problems. From a theoretical point of view, the parameter treewidth is crucial for the efficiency of such algorithms. To be more precise, the width of the tree decomposition actually used is assumed to be a key ingredient towards performance. However, experience shows that dynamic programming algorithms often exhibit a high runtime variance when using different tree decompositions; in fact, given an instance of the problem at hand, even decompositions of the same width might yield extremely diverging solving times. This means that, besides the width, there must be other features of tree decompositions which affect the performance of dynamic programming algorithms. Hence, in practice, the quality of a tree decomposition cannot be judged without taking its shape and the concrete algorithm in which the decomposition is used into account. We thus propose in this thesis the concept of what we call customized tree decompositions, i.e., tree decompositions which reflect certain preferences with regard to custom quality criteria. We present in this work two approaches which allow to reliably boost both efficiency and robustness of dynamic programming algorithms. The first approach employs techniques from the area of machine learning. We identify a large set of tree decomposition features and use machine learning for predicting the runtime of dynamic programming algorithms based on these features. Extensive experiments conducted in this context underline that customized tree decompositions obtained by selecting promising decompositions according to this strategy are highly beneficial. The second approach then aims for the fast computation of such beneficial tree decompositions. For this reason we present here a flexible and efficient software framework for computing graph decompositions which allows to easily obtain decompositions perfectly tailored towards the algorithm in which they are used. Also in the experiments concerning this second approach, the use of customized tree decompositions significantly improves the performance of the dynamic programming algorithms.