Parameterized Algorithms (WS 2021/22)

Syllabus

Many practical problems are NP-hard and are considered "intractable" by complexity theory, meaning that there is probably no polynomial time algorithm to solve the problem exactly on all instances.

Traditionally one way to deal with this difficulty is to resort to approximate solutions while retaining the polynomial running time holy cow.

Sometimes, however, exact solutions are absolutely needed in praxis and tools like CPLEX as well as specialized optimization software show that hard problems can often be solved practically. One reason for this paradox might be that the hard instances that provide for the NP-hardness of the problem are not among those that occur in practice, which is not very surprising if you have looked at several NP-completeness proofs.

Classical complexity theory only takes notice of the length of an instance and measures the runtime or other resource as a function of this length. In parameterized complexity an additional parameter that is a function of the instance is used as well to measure how hard the instance at hand really is. The running is the a function on the input length as well as its parameter. A good parameterized algorithm has a running time that is polynomial in the input length and moderately superpolynomial in the parameter. In that way the running time can be quite practible when restricted to inputs with a small parameter.

Often we can model problems using a parameter that is small for practical purposes and find an algorithm that is fast if the parameter is indeed small. Take for an example the data cleaning problem: You have n data samples from some physical experiment. Due to measurement errors some data points make no sense. To be more precise: there can be a pair of data points that contradict themselves. The goal is to delete as few data points as possible to get rid of all conflicts. As a parameterized problem we can state this as follows: The input consists of n data points and a number k. The parameter is k. The questions is whether we can delete up to k data points to make the data consistent.

In practice $n$ can be very big, but we expect $k$ to be quite small. This problem is NP-complete, but we can easily find an algorithm that runs in time \(O(2^k*n)\), which is quite fast for practical values of $k$.

In this lecture you will learn how the basic techniques to design such parameterized algorithm and about the limits of the approach.

Slides

Exercises

Exam Examples

Prerequisites

Basic knowledge in the design of efficient algorithm and their analysis. A bachelors degree in computer science or a related field.