News
Exercise sheet #5Written on 25.01.22 by Dániel Marx The fourth exercise sheet is available here. The deadline is February 1. |
Exercise sheet #4Written on 11.01.22 by Dániel Marx The fourth exercise sheet is available here. The deadline is January 18. |
No lecture on January 4Written 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 #3Written 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 #2Written on 09.11.21 by Dániel Marx The second exercise sheet is available here. The deadline is November 16. |
Exercise sheet #1Written on 26.10.21 by Dániel Marx The first exercise sheet is available here. The deadline is November 2. |
Zoom linkWritten on 19.10.21 by Dániel Marx The Zoom link for the lecture (starting 10:15 on every Tuesday): https://cs-uni-saarland-de.zoom.us/j/95438071574?pwd=RFpGdXVydFJqMXQrU2w5NnVyQzg1UT09 |
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.
Format
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
Prerequisites
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).