Abstract
In this talk we show how to efficiently utilize structure for combinatorial problem solving. We mainly focus on the prominent measure treewidth and the answer set programming framework, thereby establishing tight runtime upper and lower bounds for treewidth, under reasonable assumptions in complexity theory. These bounds will be presented in the context of decomposition-guided reductions, which are polynomial-time reductions that are guided along a specific structural representation, i.e., a tree decomposition, of the instance. In the course of this talk we also show empirical results in order to underline the role of structure in solving computationally hard reasoning modes like counting.