Lecture: Wed 14:00 via zoom
Tutorial: Wed 15:40 via zoom
By email appointment.
Oct 7th: Introduction (chapter 1 in [1])
Oct 14th: Kernelization (chapters 2.1, 2.2.1, 2.5 in [1])
Oct 21st: Bounded search trees (intro to chapter 3 {p. 51-52} and chapters 3.3, 3.4 in [1])
Nov 4th: Iterative compression (chapters 4.1, 4.3.1, 4.4 in [1])
Nov 11th: Dynamic programming and convolutions (chapters 6.1, 10.1 in [1])
Nov 18th: Treewidth (chapters 7.2, 7.3.1, 7.7.1, 7.7.2 in [1])
Nov 25th: The W-hierarchy (chapters 13.1, 13.2, 13.3 in [1])
Dec 2nd: The exponential-time hypothesis (chapters 14.1, 14.2, 14.3.1, 14.4 {for 14.4.1 only Grid Tiling and Grid Tiling with Inequality} in [1])
Dec 9th: Runtime lower bound for k-Center in planar graphs (sections 1, 2 in [4])
Dec 16th: Parameterized approximation of k-Center in low highway dimension graphs (sections 1, 2, 3 in [2])
Jan 6th: Lossy kernelization (sections 1, 2, 4, 6.2, 10 in [3])
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).
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).
Semi-oral at the end of the term. In exceptional cases there is the option of doing the exam remotely via zoom (or similar).