Lecture: Wednesdays 12:20 in S8
Tutorial: Wednesdays 14:00 in S8
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])
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])
Kernelization lower bounds (chapter 15.1, 15.2.2 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])
3.10.2018: The Vertex Cover problem and several ways how to solve it, formal definition of FPT and XP algorithms, outlook of course
10.10.2018: Kernels and their definition, kernel with 3k vertices for Vertex Cover based on crown decompositions, kernel with 2k vertices for Vertex Cover based on LPs.
17.10.2018: Feedback Vertex Set, Vertex Cover with above-LP parameterization, Odd Cycle Transversal
24.10.2018: Iterative compression and the Disjoint-P problem, improved algorithms for Feedback Vertex Set and Odd Cycle Transversal
31.10.2018: dynamic programming over subsets for Set Cover, and Weighted Steiner Tree, inclusion-exclusion for Hamiltonian Cycle, Unweighted Steiner Tree, and k-Colouring.
7.11.2018: dynamic programming on nice tree decompositions, excluded grid minor theorem for planar graphs, subexponential time FPT algorithm for Vertex Cover in planar graphs
14.11.2018: contraction-closedness and bidimensionality, parameterized reductions: Multicoloured Clique and Independent Set, Dominating Set
21.11.2018: cross compositions and polynomial compressions, polynomial parameter transformations: Steiner Tree
28.11.2018: ETH and the sparsification lemma, consequences for FPT algorithms, runtime lower bound for Clique, Planar 3-SAT and consequences for FPT algorithms for planar graphs, Grid Tiling
5.12.2018: runtime lower bound for k-Center on planar graphs, parameterized optimization problems, the highway dimension
19.12.2018: 3/2-approximation of k-Center in low highway dimension graphs
9.1.2019: approximate pre-processing algorithms via reduction and lifting algorithms, reduction rules and approximation, applications: PSAKS for Vertex Cover, Connected Vertex Cover, and Steiner Tree
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.