Thursdays 14:00 to 15:30 (lecture) and 15:40 to 17:10 (tutorial) on the 2nd floor corridor (S221)
By email appointment.
Introduction (chapter 1 in [1])
Kernelization (chapters 2.1, 2.2.1, 2.3, 2.5 in [1])
Bounded search trees (chapters 3.3, 3.4 in [1])
Iterative compression (chapters 4.1, 4.3.1, 4.4 in [1])
Randomized methods (chapters 5.1, 5.2, 5.3, 5.5, 5.6 in [1])
Dynamic programming and convolutions (chapters 6.1, 10.1 in [1])
Treewidth (chapters 7.2, 7.3.2, 7.7.1, 7.7.2 in [1])
The W-hierarchy (chapters 13.1, 13.2, 13.3, 13.6.3 example 2 in [1])
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)
Parameterized approximation of k-Center in low highway dimension graphs (sections 1, 2, 3 in [2])
Lossy kernelization (sections 1, 2, 4, 6.2, 10 in [3])
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
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)
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).
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).
Oral on appointment.