Exercise sheet #5

Written on 25.01.22 by Dániel Marx

The fourth exercise sheet is available here. The deadline is February 1.

Exercise sheet #4

Written on 11.01.22 by Dániel Marx

The fourth exercise sheet is available here. The deadline is January 18.

No lecture on January 4

Written on 04.01.22 by Dániel Marx

As it was announced during the last lecture, there will be no lecture on January 4, 2022.

Exercise sheet #3

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

The third exercise sheet is available here. The deadline is December 07.

Exercise sheet #2

Written on 09.11.21 by Dániel Marx

The second exercise sheet is available here. The deadline is November 16.

Exercise sheet #1

Written on 26.10.21 by Dániel Marx

The first exercise sheet is available here. The deadline is November 2.

Zoom link

Written on 19.10.21 by Dániel Marx

The Zoom link for the lecture (starting 10:15 on every Tuesday):

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.

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.


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


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    
October 26  L02: Introduction II Slides Video  2.1, 2.2.1, 3.5, 5.1, 5.2 Sheet 1 November 02
November 02  L03: Introduction III Slides Slides Video  4, 6.1    
November 09  L04: Lower bounds Slides Video 13.1, 13.2, 13.3, 13.6, 14.1, 14.2, 14.3 Sheet 2 November 16
November 16  L05: Kernelization I Slides Video 2.1,2.2, 2.6    
November 23  L06: Kernelization II Slides Video 2.3.1,2.4, 2.5    
November 30  L07: Kernelization III Slides Slides Video 9.1,15.1,15.2.2 Sheet 3 December 07
December 07  L08: Algebraic Methods Slides (slide 19 has been updated)Video  10.1.1,10.1.2,10.4.1    
December 14  L09: Representative sets and matroids Slides Video 12.1, 12.1.1, 12.1.2, 12.1.3, 12.3, 12.3.1, 12.3.2 No sheet  
January 11  L10: Important Cuts Slides Video 8.1, 8.2, 8.3, 8.5, 8.6 Sheet 4 January 18
January 18  L11: Treewidth I Slides Video 7.1-7.4    
January 25  L12: Treewidth II Slides Video 11.2.1,14.5.2, 13.6.2 Sheet 5 February 1
February 01  L13: Treewidth III Slides Video 7.7    
February 08  L14: Turing and Lossy Kernelization Slides Slides Video 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.