**Monday, 18.10.2021 23:59**.

## News

*Currently, no news are available*

## Parameterized Algorithms

This course is about designing fast algorithms for NP-hard graph theoretic problems, where the running time depends on multiple parameters of the input. For example, while a database may contain a very large amount of data, the size of the database queries is typically extremely small in comparison. The aim would be to obtain algorithms that have a small dependence on the database size, but possibly a larger dependence on the query size. Such an algorithm would be fast when the queries are small.

We will see several algorithmic techniques to design fast algorithms for NP-hard problems in this setting, called *Fixed Parameter Tractable (FPT) algorithms*, as well as an overview of the lower-bound methods. We will also learn about preprocessing or data-reduction algorithms in this setting, called *Kernelization algorithms*, which run in polynomial time and reduce a given instance of a NP-hard problem to an equivalent but much smaller instance.

**Format**

Two hours of lectures every week and two hours of tutorials every other week.

**Prerequisites**

Basic knowledge of algorithms, graph theory and probability will be assumed.