Introduction to Parameterized Algorithms (winter 2021)

Time and place:

Lecture: Fridays 9:00 CET in S8

Tutorial: Fridays 10:40 CET in S8

Office hours:

Online on Mondays at 15:40 CET via the following link (for the passcode, please refer to the email sent to you at the beginning of the semester):

https://cesnet.zoom.us/j/99053054290

Syllabus (with references) and lectures

1. Oct 8th: Introduction (chapter 1 in [1])

2. Oct 15th: Kernelization (chapters 2.1, 2.2.1, 2.5 in [1])

3. Oct 22nd: Bounded search trees (intro to chapter 3 {p. 51-52} and chapters 3.3, 3.4 in [1])

4. Oct 29th: Iterative compression (chapters 4.1, 4.3.1, 4.4 in [1])

5. Nov 5th: Dynamic programming and convolutions (chapters 6.1, 10.1 in [1])

6. Nov 12th: Treewidth (chapters 7.2, 7.3.1, 7.7.1, 7.7.2 in [1])

7. Nov 26th: The W-hierarchy (chapters 13.1, 13.2 {only pages 426 to 430}, 13.3 in [1])

8. Dec 3rd: The exponential-time hypothesis (chapters 14.1, 14.2, 14.3.1, 14.4 {only pages 485 to 487, and in 14.4.1 only theorems 14.28 and 14.30} in [1])

9. Dec 10th: Runtime lower bound for k-Center in planar graphs (sections 1, 2 in [4])

10. Dec 17th: Parameterized approximation of k-Center in low highway dimension graphs (sections 1, 2, 3 in [2])

11. Jan 7th: Lossy kernelization (sections 1, 2, 4, 6.2 in [3])

Literature

1. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015, ISBN 978-3-319-21274-6 (downloadable with university account)

2. Andreas Emil Feldmann: Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP).

3. Daniel Lokshtanov, Fahad Panolan, M.S. Ramanujan, Saket Saurabh: Lossy Kernelization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC).

4. Andreas Emil Feldmann, Dániel Marx: The Parameterized Hardness of the k-Center Problem in Transportation Networks. In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT).

Exam

Semi-oral at the end of the term. In exceptional cases there is the option of doing the exam remotely via zoom (or similar).

Exercise Sheets