Introduction to Parameterized Algorithms (winter 2019)

Time and place:

Lecture: Thursdays 10:40 in S8

Tutorial: Thursdays 12:20 in S11

Office hours:

By email appointment.

Syllabus (with references)

  1. Introduction (chapter 1 in [1])

  2. Kernelization (chapters 2.1, 2.2.1, 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. 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])

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

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

Lectures

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

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