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 |
| 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 |
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)
| Date | Topic | Material | Reference (see below) | Exercise | Due |
|---|---|---|---|---|---|
| May 8 | L01: Introduction I | Slides | Ch. 1, 2.1, 2.2, 3.1, 3.2, 3.3, 5.2 | Sheet 1 (L01) | May 15 |
| May 15 | L02: Introduction II | Slides | Ch. 4, 6.1 | ||
| May 22 | L03: Lower Bounds | Slides | Ch. 13.1, 13.2, 13.3, 13.6, 14.1, 14.2, 14.3 | Sheet 2 (L02 + L03) | May 29 |
| May 29 | L04: Kernelization I | Slides | Ch. 2.1, 2.2.1, 2.2.2, 2.3.2, 2.4, 2.6, 9.1 | ||
| June 5 | L05: Kernelization II | Slides | Ch. 2.3, 2.5, 9.3, 15.1, 15.2.2 | Sheet 3 (L04 + L05) | June 12 |
| June 12 | L06: Algebraic Methods | Slides | Ch 10.1, 10.1.2, 10.4, 10.4.1 | ||
| June 19 | L07: Treewidth I | Slides | Ch. 7.1-7.4, 14.5.2 | ||
| June 26 | L08: Treewidth II | Slides | Ch. 7.7 | Sheet 4 (L07 + L08) | July 3 |
| July 3 | L09: Important Cuts | Slides | Ch. 8.1, 8.2, 8.3, 8.5, 8.6 | Sheet 5 (L09) | July 10 |
| July 10 | L10: Matroids | Ch. 12.1, 12.3, 12.6 | |||
| July 17 | L11: Turing Kernels and Lossy Kernels | Slides | Ch. 9.4, [LPRS] |
Material
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]