Dániel Marx

Lehre von Dániel Marx

Winter 2021/22

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.

Lectures: Tuesday, 10:15-12:00, online over Zoom

First lecture: October 19, 2021

Prerequisites

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

Date	Topic	Material	Reference (see below)	Exercise	Due
October 19	L01: Introduction I	Slides Video	1, 3.1, 3.2, 3.3

 

Reference Textbook

"Parameterized Algorithms" by Cygan et al. (see this for free pdf of the book from the authors).