Lecture: Thursdays 10:40 in S8
Tutorial: Thursdays 12:20 in S11
By email appointment.
Introduction (chapter 1 in [1])
Kernelization (chapters 2.1, 2.2.1, 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])
Dynamic programming and convolutions (chapters 6.1, 10.1 in [1])
Treewidth (chapters 7.2, 7.3.1, 7.7.1, 7.7.2 in [1])
The W-hierarchy (chapters 13.1, 13.2, 13.3 in [1])
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] & sections 1, 2 in [4])
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])
10.10.2019: the Vertex Cover problem and several ways how to solve it, formal definition of FPT and XP algorithms, outlook of course
17.10.2019: definition of kernels, equivalence to FPT algorithms, Nemhauser-Trotter theorem and application to kernels for Vertex Cover, bounded search trees
24.10.2019: solving Feedback Vertex Set, Vertex Cover above LP, and Odd Cycle Transversal using bounded search trees
31.10.2019: iterative compression for Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal
7.11.2019: dynamic programming for Set Cover and Steiner Tree, convolution algorithms for Hamiltonian Cycle and Unweighted Steiner Tree
14.11.2019: dynamic program for Independent Set on nice tree decompositions, grid-minor theorem, subexponential time algorithm for Vertex Cover in planar graphs, contraction-closedness of Dominating Set
28.11.2019: bidimensionality and subexponential time algorithms, parameterized reductions from Clique, complexity class W[t], exponential time hypothesis
5.12.2019: sparsification lemma, runtime lower bounds for problems in FPT, for Clique, for planar problems in FPT, and for Grid Tiling
19.12.2019: runtime lower bound for k-Center in planar graphs, the highway dimension, hardness of k-Center parameterized by k and the highway dimension, parameterized 3/2-approximation for k-Center
9.1.2020: parameterized 3/2-approximation for k-Center, approximate kernelization, PSAKS for Connected Vertex Cover
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.