Tutorials are led by Tung Anh Vu. 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] |
|---|---|
| 1. 10. | Introduction to parameterized algorithms / complexity. [PA 1] |
| 8. 10. | Kernelization [PA 2.1, 2.2.1, 2.3-intro, 2.3.1]. Crown decomposition lemma proof was from [Ker, Lemma 4.5] |
| 15. 10. | FPT algorithm for Vertex Cover above LP [PA 3.4], |
| 22. 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] |
| 29. 10. | Iterative Compression for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal, [PA 4.1, 4.3.1, 4.4] |
| 5. 11. | sport day - no class |
| 12. 11. | Dynamic programming and convolutions on Set Cover and Steiner Tree [PA 6.1], PIE and Hamiltonian Cycle [PA 10.1.1] |
| 19. 11. | Treewidth, nice tree decompositions, Independent Set [PA 7.2, 7.3.1] |
| 26. 11. | More Treewidth - grids, bidimensionality [PA 7.7.1, 7.7.2 ] |
| 3. 12. | Intro to neighborhood diversity and ILPs. Solving Coloring on graphs of bounded $nd(G)$. [ND, NdCol, 5M] |
| 10. 12. | Neighborhood diversity: Sum Coloring via $n$-fold IP, and as a convex IP in small dimension [5M, Thm 2(a), 2(b)] |
| 17. 12. | Plan: Neighborhood diversity: Q&A on Sum Coloring [5M, Thm 2], Capacitated Dominating Set [5M, Thm 1]; Max $q$-Cut [5M, Thm 3]. Geogebra: $x \cdot y$ is obviously not convex. |
| 7. 1. | Plan: $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)$). |