Parameterized Algorithms (SS 2015)

Course Description

It is a (sad) empirical fact that most computational problems that are motivated by real-life problems are (at least!) NP-hard. So they cannot—using current algorithmic technology—be solved exactly within "reasonable" time bounds. How do we cope with this pervasive (and seemingly inescapable) hardness?

In this course, we introduce you to a very successful approach for solving hard problems fast: parameterized algorithms. The primary motivation for this approach is the observation that the computational hardness of many hard problems can be "isolated" to one or more aspects or parameters of the problem. During the course, we will explore algorithmic and structural techniques that can take advantage of this observation. In particular, we will discuss:

1. Parameterized Algorithms: algorithms whose running times are exponential only in the chosen parameter, and are polynomial in the instance size. If the parameter is "small" in real-life inputs, then this leads to fast exact algorithms that work well in practice.
2. Kernelization Algorithms: algorithms that reduce the size of the problem to a (hopefully small) function of the parameter. This provides a theoretical framework to understand the power of preprocessing heuristics.
3. Hardness: How can we prove that certain problems do not have a parameterized or kernelization algorithm for a particular parameter?

Parameterized Algorithms is a very lively field of current research.

Basic Information

Schedule

Note that the schedule is dense during the first half of the semester, and not so much during the second half.
Topics on future dates are tentative.