Exploiting new types of structure for fixed-parameter tractability

Abstract

The design of efficient algorithms for various problems is a fundamental part of computer science. One significant obstacle in this area is the fact that many interesting problems from areas such as Algorithmic Graph Theory, Artificial Intelligence, or Optimization are known to be NP-hard on general instances. However, in the majority of applications the instances of interest are the result or output of some other processes, and as such inherently contain some form of structure. This structure can often be exploited to efficiently find exact solutions for many NP-hard problems. To capture the structure of the input instance, we use the framework of parameterized complexity. In parameterized algorithms, the running time is analyzed in finer detail than in classical complexity theory: instead of expressing the running time as a function of the input size only, dependence on a parameter k is taken into account. We use the parameter k to describe how “structured” the input instance is. Algorithms with running time f(k)nc, where n is the input size and c is a constant independent of both n and k, are called fixed-parameter algorithms or FPT algorithms. Typically the goal in parameterized algorithms is to design FPT algorithms while minimizing both the f(k) factor and the constant c in the bound on the running time. We study a range of different problems under the paradigm of parameterized complexity. More precisely, our research focuses on two approaches to analyze the structure of instances and their combination. The first approach focuses on the notion of decomposition. The idea is to decompose the given input into simpler parts and use this decomposition to solve the problem more efficiently. The second approach is based on the established notion of a modulator to a tractable class of instances, which applies to problem instances that may be placed in a tractable class by a small number of local changes. We design several algorithms that exploit some of the already established parameters. However, our main focus is on designing and exploiting new kinds of structure. We highlight here one of the results in particular. We develop a family of parameters that combine the two approaches outlined above to capture forms of structure not accessible to a single approach, and we show that these parameters give rise to efficient algorithms for a plethora of NP-hard problems.