Exact exponential and parameterized algorithms

("Dealing with hard problems")

The goal of algorithm design is to come up with efficient algorithms for problems that arise in applications. By efficient, we usually mean "polynomial running time for every instance". Unfortunately several (or even most) of the natural problems that we want to solve are NP-hard, and thus finding polynomial-time algorithms for them is hopeless.

Two broad approaches for dealing with this situation, when approximations are not acceptable, are exact exponential algorithms, and parameterized algorithms. In the first case, we look for algorithms that solve the problem in exponential time, but faster than a trivial brute force approach. In the second case, we try to identify meaningful parameters, so that the exponential growth in running time is limited to these. 

In this course we review important techniques and results from both fields, including recent developments. The lectures will be given in English, and the course will (likely) be remote/online.

Literatur

* Fomin, Kratsch: Exact Exponential Algorithms, Springer 2010.

Freely available here: https://folk.uib.no/nmiff/BookEA/download.html

* Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh: Parameterized Algorithms, Springer 2015.

Freely available here: https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf

* research articles, references to be given later.

Zielgruppe

Informatiker und interessierte Mathematiker im Masterstudium.

Empfohlene Vorkennntnisse

"Höhere Algorithmik" oder eine andere Vorlesung ähnlichen Inhalts.

Course links

Lecture meetings:

https://fu-berlin.webex.com/fu-berlin-en/j.php?MTID=ma9bf85a1bb385a350ea9522d3658d394

Exercise meetings:

https://fu-berlin.webex.com/fu-berlin-en/j.php?MTID=m7f01e1891a813bd4cef44831976485d9

Offline material:

https://nextcloud.imp.fu-berlin.de/index.php/s/HfWXNzHQqHtywYo