Introduction to Parameterized Algorithms 26/27

Tutorial sessions

Tutorials are led by Martin Koreček, where you can find materials from the tutorial sessions and instructions on how to solve homework.

date	what was said [source]
1. 10.	Introduction to parameterized algorithms / complexity. [PA 1] I mentioned this connection between parameterized and exponential algorithms
9. 10.	Kernelization, Vertex Cover kernel of size $3k$ via crown decomposition [PA 2.1, 2.2.1, 2.3-intro, 2.3.1]
16. 10.	Kernel for Vertex Cover by LP [PA 2.5], FPT algorithm for Vertex Cover above LP [PA 3.4]
23. 10.	Bounded Search Trees: Feedback Vertex Set in $\mathcal{O}^( (3k)^k)$ time; Closest String in $\mathcal{O}^(d^d)$ time [PA 3.3, 3.5]

[PA] is the book Parameterized Algorithms.
[ND] Algorithmic Meta-theorems for Restrictions of Treewidth: a paper which introduced $nd(G)$ and describes the coloring algorithm
[NdCol] A note on coloring...: a paper by Martin which retells the coloring algorithm by Lampis and points out that it can be solved more efficiently
[5M] Integer programming in parameterized complexity: Five miniatures a comprehensive paper about various parameterized integer programming algorithms and their applications to problems on bounded-$nd$ graphs.
[GR] Polynomiality for Bin Packing with a Constant Number of Item Types