Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Parameterized Algorithms

MSc Lecture - Summer 2024

Description

While many popular algorithms work in polynomial time, most of the natural problems are NP-hard, that is, (most probably) they do not admit polynomial-time algorithms. This course is dedicated to an approach that aims to overcome the NP-hardness barrier while still retaining provable guarantees on the algorithm.

More precisely, parameterized complexity achieves this by introducing another measure of the input called the parameter. The running time of the algorithm is then measured as some function of the parameter k and the input size n. The main target of the theory is a fixed-parameter tractable (FPT) algorithm, working in time f(k) · poly(n) for some function f of k. In practice, the dependency is often single-exponential in k and linear in n, leading to algorithms that are quite efficient as long as k is reasonably small. For example, while the Vertex Cover problem is NP-hard on general graphs, it admits an FPT algorithm running in time O(1.2738k + k · n), where k is the size of the vertex cover – which is still practical for pretty large graphs with a vertex cover of size up to 190.

In fact, the parameter needs not to be the solution size or something similarly explicit in the input, but rather could be an arbitrary property of the instance. A prominent example is the treewidth of a graph, which intuitively measures how tree-like the graph is. There are however, many other width measures capturing other structural properties of graphs, and in general many other ways to exploit the parameterized viewpoint to achieve tractability for a generally hard problem.

Throughout the course, we will cover most of the fundamental aspects of the parameterized complexity theory, starting from the basics and (gently) leading into currently active research topics by the end of the course. The list of topics encompasses algorithmic techniques, such as branching, linear programming, color coding, dynamic programming over various decompositions; kernelization a.k.a. parameterized preprocessing; and lower bounds, i.e., methods to rule out the existence of certain parameterized algorithms.

 

Requirements

The course is especially suited for those curious to get familiar with cutting-edge areas in algorithmic and graph-theoretic research. As this is a theory course, we expect familiarity with mathematical notation, graphs and basic algorithms. Selected topics will touch on probabilistic and algebraic methods. Lectures and all materials will be in English.

 

Grading

The grade will be determined by a written midterm and the final oral exam. There will also be optional weekly/biweekly exercises.

 

Meetings

We meet weekly on Wednesday, 13:30-15:00, and Thursday, 13:30-15:00. The first meeting will be Wednesday, April 10.