Parameterized Algorithms

Advanced Course, 2+1

Basic Information

Lectures:(Online) Friday 2PM to 4PM at Room E1.4 024 (tentative)
Lecturers:Daniel Marx and Pranabendu Misra
First lecture:May 8, 2020
Tutorials:Tuesday, 14:15 (Once every 2 weeks)
Teaching Assistant:Philip Wellnitz
First tutorial:May 19
Exam:Oral Exam
Prerequisites:Basic knowledge of algorithms, graph theory and probability will be assumed. 
Mailing List:

It is mandatory for students to signup for the course mailing list 
Please subscribe here: 



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.

Schedule (lectures)

DateTopicMaterialReference (see below)ExerciseDue
May 8L01: Introduction ISlidesCh. 1, 2.1, 2.2, 3.1, 3.2, 3.3, 5.2Sheet 1 (L01)May 15
May 15L02: Introduction IISlidesCh. 4, 6.1  
May 22L03: Lower BoundsSlidesCh. 13.1, 13.2, 13.3, 13.6, 14.1, 14.2, 14.3Sheet 2 (L02 + L03)May 29
May 29L04: Kernelization ISlidesCh. 2.1, 2.2.1, 2.2.2, 2.3.2, 2.4, 2.6, 9.1  
June 5L05: Kernelization IISlidesCh. 2.3, 2.5, 9.3, 15.1, 15.2.2Sheet 3 (L04 + L05)June 12
June 12L06: Algebraic MethodsSlidesCh 10.1, 10.1.2, 10.4, 10.4.1  
June 19L07: Treewidth ISlidesCh. 7.1-7.4, 14.5.2  
June 26L08: Treewidth IISlidesCh. 7.7Sheet 4 (L07 + L08)July 3
July 3L09: Important CutsSlidesCh. 8.1, 8.2, 8.3, 8.5, 8.6Sheet 5 (L09)July 10
July 10L10: Matroids

Slides_1  Slides_2

Ch. 12.1, 12.3, 12.6  
July 17

L11: Turing Kernels and Lossy Kernels

SlidesCh. 9.4, [LPRS]  


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

[LPRS]: Lossy Kernelization - STOC 2017 [arxiv]