Introduction to Parameterized Algorithms (winter 2018)

Time and place:

Lecture: Wednesdays 12:20 in S8

Tutorial: Wednesdays 14:00 in S8

Office hours:

By email appointment.

Syllabus (book chapters)

  1. Introduction (chapter 1 in [1])

  2. Kernelization (chapters 2.1, 2.2.1, 2.3, 2.5 in [1])

  3. Bounded search trees (chapters 3.3, 3.4 in [1])

  4. Iterative compression (chapters 4.1, 4.3.1, 4.4 in [1])

  5. Dynamic programming and convolutions (chapters 6.1, 10.1 in [1])

  6. Treewidth (chapters 7.2, 7.3.1, 7.7.1, 7.7.2 in [1])

  7. The W-hierarchy (chapters 13.1, 13.2, 13.3 in [1])

  8. Kernelization lower bounds (chapter 15.1, 15.2.2 in [1])

  9. 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])

  10. Parameterized approximation of k-Center in low highway dimension graphs (sections 1, 2, 3 in [2])

  11. Lossy kernelization (sections 1, 2, 4, 6.2, 10 in [3])

Lectures

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

Literature

  1. 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)

  2. 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).

  3. 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).

  4. 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).

Exam

Semi-oral at the end of the term.

Exercise Sheets