News
30.05.2023

Lecture delayed by 15 minutesToday (30.5) the lecture will start at 10:30 due to an emergency situation. Thank you for your understanding. 
23.05.2023

Exercise sheet #3The third exercise sheet is available here. The deadline is May 30. 
16.05.2023

Exercise #3Exercise #3 will be out next week after the lecture. There will be no exercise sheet today (this week). 
02.05.2023

Exercise sheet #2The second exercise sheet is available here. The deadline is May 9. 
18.04.2023

Exercise sheet #1The first exercise sheet is available here. The deadline is April 25. As announced, 50% of all points on the exercise sheets are needed to be admitted to the (oral) exam. 
Parameterized Algorithms
This course is about designing fast algorithms for NPhard 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. Similarly, if the goal is to find small solutions in a large graph, then an algorithm with exponential dependence on the size of the solution and polynomial dependence on the size of the graph might be acceptable.
We will see several algorithmic techniques to design fast algorithms for NPhard problems in this setting, called FixedParameter Tractable (FPT) algorithms, as well as an overview of the lowerbound methods. We will also learn about preprocessing or datareduction algorithms in this setting, called Kernelization algorithms, which run in polynomial time and reduce a given instance of a NPhard problem to an equivalent but much smaller instance.
Some example topics that will be covered during the course:
 Branching, boundeddepth search trees
 Randomization, color coding
 Iterative compression
 Kernelization, sunflower lemma, crown decomposition
 Kernelization lower bounds
 Algebraic methods, inclusionexclusion
 Representative sets and matroids
 Important cuts
 Treewidth, bidimensionality on planar graphs
 Turing and lossy kernelization
Format
Two hours of lectures every week and two hours of tutorials every other week. During the semester, 5 homework exercise sheets will be handed out, to be submitted in one week. 50% of all points on the exercise sheets are needed to be admitted to the (oral) exam. The solutions of the exercises are discussed in the tutorial sessions (after the deadline).
Lectures: Tuesday, 10:1512:00
Tutorial: To be decided
First lecture: April 11, 2023
Room: E 1 4 (MPIINF) 021
Prerequisites
Basic knowledge of algorithms, graph theory and probability will be assumed.
Date  Topic  Material  Reference (see below)  Exercise  Due 

April 11  L01: Introduction I  Slides  1, 3.1, 3.2, 3.3  
April 18  L02: Introduction II  Slides  2.1, 2.2.1, 3.5, 5.1, 5.2  Sheet 1  April 25 
April 25 
L03: Introduction III 
Slides  6.1, 4.1, 4.2, 4.3.1, 4.4  
May 2 
L04: Lower Bounds 
Slides  13.1, 13.2, 13.3, 13.6, 14.1, 14.2, 14.3  Sheet 2  May 9 
May 9 
L05: Kernelization I 
Slides  2.1, 2.2, 2.6  
May 16 
L06: Kernelization II 
Slides  2.3.1, 2.5, 2.4  
May 23 
L07: Kernelization III 
Slides  9.1, 15.1 (intro)  Sheet 3  May 30 
May 30 
L08: Kernelization Lower Bounds 
Slides  15.1,15.2.2 
Reference Textbook
"Parameterized Algorithms" by Cygan et al. (see this for free pdf of the book from the authors).