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