Tighter Algorithms for Decompositional Graph Parameters

The high-level idea of decomposing a graph into parts, which behave favourably internally as well as in their interactions, combines naturally with many funda- mental algorithmic paradigms such as dynamic programming or divide&conquer type approaches. Taking this abstract approach to a more systematic level has led to the definition of so called decompositional parameters. These can be thought of as concrete numeric measures for how difficult it is to ensure the desired favourable behaviour within a decomposition of the input. The vast majority of algorithms that solve a problem by exploiting the struc- ture implied by decompositional parameters work in a two-step approach: First a decomposition realising the respective parameter is computed, and then, this decomposition is used to solve the problem. This project targets what we believe are key questions for understanding the precise complexity of such approaches. For this, we follow the relatively young but already extremely fruitful paradigm of fine-grained parameterised complex- ity theory. To date the study of fine-grained parameterised complexity has predominantly focussed on the second step. Our first goal is to analyse the first step for a set of important decompositional parameters and close or at least tighten the comparatively huge gaps in what we know about the complexity of computing their corresponding decompositions. Our second goal is to develop a general framework to understand the general power and limitations of some im- portant decomposition-based algorithmic techniques that have been previously developed in the field of fine-grained parameterised complexity.