Parameterized Algorithms

Advanced Course, 2+1

Basic Information

Lectures:(Online) Friday 2PM to 4PM at Room E1.4 024 (tentative)

10th lecture: July 10 14:15
(Zoom meeting starts at 14:10)

https://cs-uni-saarland-de.zoom.us/j/95146485942?pwd=cHVFczdPVmQ1a1RjYlF2c1FBUXRxUT09

Meeting ID: 951 4648 5942
Password: 241049

Lecturers:Daniel Marx and Pranabendu Misra
First lecture:May 8, 2020
Tutorials:Tuesday, 14:15 (Once every 2 weeks)
Assistant:Philip Wellnitz
First tutorial:May 19
Credits:5
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:  https://lists.mpi-inf.mpg.de/listinfo/fptalgo20 

Description

 

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 textbook below)ExerciseDue
May 8L01: Introduction ISlides  VideoCh. 1, 2.1, 2.2, 3.1, 3.2, 3.3, 5.2Sheet 1 (L01)May 15
May 15L02: Introduction IISlides  VideoCh. 4, 6.1  
May 22L03: Lower BoundsSlides  VideoCh. 13.1, 13.2, 13.3, 13.6, 14.1, 14.2, 14.3Sheet 2 (L02 + L03)May 29
May 29L04: Kernelization ISlides  VideoCh. 2.1, 2.2.1, 2.2.2, 2.3.2, 2.4, 2.6, 9.1  
June 5L05: Kernelization IISlides  VideoCh. 2.3, 2.5, 9.3, 15.1, 15.2.2Sheet 3 (L04 + L05)June 12
June 12L06: Algebraic MethodsSlides  VideoCh 10.1, 10.1.2, 10.4, 10.4.1  
June 19L07: Treewidth ISlides  VideoCh. 7.1-7.4, 14.5.2  
June 26L08: Treewidth IISlides  VideoCh. 7.7Sheet 4 (L07 + L08)July 3
July 3L09: Important CutsSlides  VideoCh. 8.1, 8.2, 8.3, 8.5, 8.6Sheet 5 (L09)July 10
July 10L10: Matroids

Slides_1  Slides_2    Video

Ch. 12.1, 12.3, 12.6  
July 17L11: TBA    

Material

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