Introduction to Parameterized Algorithms (winter 2022)

Time and place:

Lecture: Wednesdays at 10:40 in S6

Tutorial: Wednesdays at 14:00 in S6 led by Nicolaos Μatsakis

Office hours:

By email appointment.

Syllabus (with references) and lectures

  1. Oct 5: Introduction (chapter 1 in [1])

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

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

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

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

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

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

  8. Nov 30: 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 14: Runtime lower bound for k-Center in planar graphs (sections 1, 2 in [4])

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

  11. Jan 4: Lossy kernelization (sections 1, 2, 4, 6.2 in [3], sections 1 and 3 in [6], less technical overview: section 2 in [5])

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

  5. Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi: A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms.

  6. Al Borchers, Ding-Zhu Du: The k-Steiner Ratio in Graphs. SIAM Journal on Computing.

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