HYPAR - Hybrid Parameterized Problem Solving in Practice

Solving computationally hard problems is a key challenge in computer science. One approach towards efficient solutions relies on decomposing the problem instances into smaller parts and solving the problem step-by-step by solving parts (subproblems) via a dedicated algorithm. This dedicated algorithm then suitably combines solutions of the single parts into a solution of the problem. Think about coloring a map with a limited number of colors such that no two countries that share a border are assigned the same color. Naturally, one starts to color several regions of the map, say Scandinavia, Eastern Europe, the Balkan states etc, independently. Then, one tries to combine solutions for these regions in order to find a valid coloring of the entire map of Europe. One particular form of this method is known as dynamic programming over tree decompositions. The runtime of this approach mainly depends on a certain parameter, namely the size of the largest subproblem, which can be obtained via tree decompositions satisfying certain criteria. The common hypothesis for this approach is that the smaller the parts obtained by the decomposition are, the faster the problem at hand can be solved. However, practical experiments have shown that this theoretical rule of thumb does not necessarily apply in practice. In fact, there is a certain trade-off between the computational costs required for solving the subproblems (i.e., coloring regions) and the necessary combination of these solutions (i.e., checking which colorings of the regions go together). In fact, the theoretical analysis in this context is mainly devoted to relate runtimes with the maximum size of the subproblems. However, if subproblems become larger, their interaction with other subproblems becomes less involved, which makes the task of combining solutions easier. Our working hypothesis is that decompositions with larger subproblems might be beneficial in practice, in particular if dedicated algorithms are used to solve subproblems. Therefore, we call this approach hybrid since it relies on both standard approaches for the subproblems and the dedicated dynamic programming machinery for combining solutions to subproblems. In this project, we aim to better understand which "shapes" of decompositions provide the best results in practice, and to study methods on how to find these decompositions. Our approach will be evaluated on several prominent hard problems in the area of Computer Science.

Solving computationally hard problems is a key challenge in computer science. One approach towards efficient solutions relies on decomposing the problem instances into smaller parts and solving the problem step-by-step by solving parts (subproblems) via a dedicated algorithm. This dedicated algorithm then suitably combines solutions of the single parts into a solution of the problem. Think about coloring a map with a limited number of colors such that no two countries that share a border are assigned the same color. Naturally, one starts to color several regions of the map, say Scandinavia, Eastern Europe, the Balkan states etc, independently. Then, one tries to combine solutions for these regions in order to find a valid coloring of the entire map of Europe. One particular form of this method is known as dynamic programming over tree decompositions. The runtime of this approach mainly depends on a certain parameter, namely the size of the largest subproblem, which can be obtained via tree decompositions satisfying certain criteria. In the project, we showed that decompositions with larger subproblems nevertheless might be beneficial in practice, in particular if dedicated algorithms are used to solve subproblems. We demonstrated this effect in several solving regimes, in particular propositional logic and logic programming. For the latter, we also approached a long-standing problem, the so-called grounding bottleneck by proposing an alternative grounding method.