Introduction to Parameterized Algorithms (winter 2017)

Time and place:

Thursdays 14:00 to 15:30 (lecture) and 15:40 to 17:10 (tutorial) on the 2nd floor corridor (S221)

Office hours:

By email appointment.

Syllabus (book chapters)

  1. Introduction (chapter 1 in [1])

  2. Kernelization (chapters 2.1, 2.2.1, 2.3, 2.5 in [1])

  3. Bounded search trees (chapters 3.3, 3.4 in [1])

  4. Iterative compression (chapters 4.1, 4.3.1, 4.4 in [1])

  5. Randomized methods (chapters 5.1, 5.2, 5.3, 5.5, 5.6 in [1])

  6. Dynamic programming and convolutions (chapters 6.1, 10.1 in [1])

  7. Treewidth (chapters 7.2, 7.3.2, 7.7.1, 7.7.2 in [1])

  8. The W-hierarchy (chapters 13.1, 13.2, 13.3, 13.6.3 example 2 in [1])

  9. The exponential-time hypothesis (chapters 41.1, 14.2, 14.3.1, 14.4 {for 14.4.1 only Grid Tiling and Grid Tiling with Inequality} in [1] & hardness of k-Center in planar graphs)

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

  11. Lossy kernelization (sections 1, 2, 4, 6.2, 10 in [3])

Lectures

12.10: Introduction

19.10: Kernelization

26.10: Bounded search trees

2.11: Iterative compression

9.11: Color coding

16.11: Dynamic programming and convolutions

30.11: Treewidth

7.12: The W-hierarchy

14.12: The exponential-time hypothesis

21.12: Hardness of k-Center in planar graphs & intro to low highway dimension graphs

4.1: k-Center in low highway dimension graphs & intro to lossy kernelization

11.1: Lossy kernelization

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 access)

  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).

Exam

Oral on appointment.