Exercise sheet #5

Written on 11.07.23 by Dániel Marx

The fifth (last) exercise sheet is available here. The deadline is July 18.

Exercise sheet #4

Written on 21.06.23 by Dániel Marx

The fourth exercise sheet is available here. The deadline is June 27.

The next block of three lectures (27.6, 4.7, 11.7) will be on the combinatorial notion of treewidth and its algorithmic applications.

No lecture today

Written on 13.06.23 by Dániel Marx

As announced in the last lecture, there is no lecture today. The next lecture is on 20.6 (and the next exercise sheet will be handed out on that day).

Lecture delayed by 15 minutes

Written on 30.05.23 by Dániel Marx

Today (30.5) the lecture will start at 10:30 due to an emergency situation. Thank you for your understanding.

Exercise sheet #3

Written on 23.05.23 (last change on 23.05.23) by Roohani Sharma

The third exercise sheet is available here. The deadline is May 30.

Exercise #3

Written on 16.05.23 by Roohani Sharma

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

Exercise sheet #2

Written on 02.05.23 (last change on 23.05.23) by Dániel Marx

The second exercise sheet is available here. The deadline is May 9.

Exercise sheet #1

Written on 18.04.23 by Dániel Marx

The 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.

Show all

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. 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 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.

Some example topics that will be covered during the course:

  • Branching, bounded-depth search trees
  • Randomization, color coding
  • Iterative compression
  • Kernelization, sunflower lemma, crown decomposition
  • Kernelization lower bounds
  • Algebraic methods, inclusion-exclusion
  • Representative sets and matroids
  • Important cuts
  • Treewidth, bidimensionality on planar graphs
  • Turing and lossy kernelization


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:15-12:00

Tutorial: To be decided

First lecture: April 11, 2023

Room: E 1 4 (MPI-INF) 021


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    
June 6

 L09: Algebraic Methods

Slides 10.1.1,10.1.2,10.4.1    
June 13

 No lecture

June 20

 L10: Important Cuts

Slides 8.1, 8.2, 8.3, 8.5, 8.6 Sheet 4 June 27
June 20

 L11: Treewidth I

Slides 7.1-7.4    
July 4

 L12: Treewidth II

Slides 11.2.1,14.5.2, 13.6.2    
July 11

 L13: Treewidth III

Slides 7.7 Sheet 5 July 18
July 18

 L14: Turing and Lossy Kernelization

Slides 9.4, 23.1 and 23.4 from this book


Reference Textbook

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



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.