Introduction to Parameterized Algorithms 23/24

Tutorial sessions

Tutorials are led by Tung. 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]
5. 10.	Introduction to parameterized algorithms / complexity. [PA 1]
12. 10.	Kernelization [PA 2.1, 2.2.1, 2.3-intro, 2.3.1, 2.5 without Lemma 2.22]
19. 10.	Finishing kernels from last time. 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]*
26. 10.	FPT algorithm for Vertex Cover above LP, application: FPT algorithm for Odd Cycle Transversal [PA 3.4];
2. 11.	No class: Dean's sport day
9. 11.	Iterative Compression for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal, [PA 4.1, 4.3.1, 4.4]
16. 11.	Dynamic programming and convolutions on Set Cover and Steiner Tree [PA 6.1], PIE and Hamiltonian Cycle [PA 10.1.1]
23. 11.	Treewidth, nice tree decompositions, Independent Set [PA 7.2, 7.3.1]
30. 11.	More Treewidth - FPT alg., MSO, grids [PA 7.7.1, 7.7.2 ]
7. 12.	Intro to neighborhood diversity and ILPs. Solving Coloring on graphs of bounded $nd(G)$. [ND, NdCol, 5M]
14. 12.	Neighborhood diversity: Sum Coloring via $n$-fold IP, and as a convex IP in small dimension [5M, Thm 2(a), 2(b)]
21. 12.	Neighborhood diversity: finish Sum Coloring [5M, Thm 2], Capacitated Dominating Set [5M, Thm 1]
4. 1.	Parameterized reductions, The W-hierarchy [PA, 13.1, 13.2, 13.3]
11. 1.	$P\|\|C_{\max}$ is FPT($d$) if $p_{\max}$ unary bounded, using the algorithm of Goemans-Rothvoss [GR]. Another application: Equitable Coloring is FPT($nd(G)$).

[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