Introduction to Parameterized Algorithms 25/26

Tutorial sessions

Tutorials are led by Tung Anh Vu and Martin Koreček. Click here for the website of the tutorials, where you can find materials from the tutorial sessions and instructions on how to solve homework.

date	what was said [source]
29. 9.	Introduction to parameterized algorithms / complexity. [PA 1]
6. 10.	Kernelization [PA 2.1, 2.2.1, 2.3-intro, 2.3.1]. Crown decomposition lemma proof was from [Ker, Lemma 4.5]
13. 10.	Bounded Search Trees: Vertex Cover in $\mathcal{O}^(1.6181^k)$ and $\mathcal{O}^(1.4656^k)$ time; Closest String in $\mathcal{O}^(d^d)$ time [PA 3.1, 3.5]*
20. 10.	FPT algorithms for Feedback Vertex Set in $\mathcal{O}^((3k)^k)$ time and for Vertex Cover above LP [PA 3.4]*,

[PA] is the book Parameterized Algorithms.
[Ker] is the book Kernelization.
[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