Lecture: Wednesdays at 10:40 in S6
Tutorial: Wednesdays at 14:00 in S6 led by Nicolaos Μatsakis
By email appointment.
Oct 5: Introduction (chapter 1 in [1])
Oct 12: Kernelization (chapters 2.1, 2.2.1, 2.5 in [1])
Oct 19: Bounded search trees (intro to chapter 3 {p. 51-52} and chapters 3.3, 3.4 in [1])
Oct 26: Iterative compression (chapters 4.1, 4.3.1, 4.4 in [1])
Nov 2: Dynamic programming and convolutions (chapters 6.1, 10.1 in [1])
Nov 16: Treewidth (chapters 7.2, 7.3.1, 7.7.1, 7.7.2 in [1])
Nov 23: The W-hierarchy (chapters 13.1, 13.2 {only pages 426 to 430}, 13.3 in [1])
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])
Dec 14: Runtime lower bound for k-Center in planar graphs (sections 1, 2 in [4])
Dec 21: Parameterized approximation of k-Center in low highway dimension graphs (sections 1, 2, 3 in [2])
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])
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)
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).
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi: A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms.
Al Borchers, Ding-Zhu Du: The k-Steiner Ratio in Graphs. SIAM Journal on Computing.
Semi-oral at the end of the term. In exceptional cases there is the option of doing the exam remotely via zoom (or similar).