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] |
|---|---|
| 2. 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] |
| 30. 10. | Chromatic Number under structural parameters. Since 3-Coloring is NP-hard, the number of colors alone does not help. Parameters: vertex cover $vc$, neighborhood diversity $nd$ and treedepth $td$ (defined), treewidth $tw$ and clique-width $cw$ (stated), and how they compare (the parameter poset). FPT algorithms for Chromatic Number by $vc$, by $td$ (branching along an elimination forest, polynomial space) and by $nd$ (ILP in fixed dimension) [ND, NdCol]. Kernels: Chromatic Number has a polynomial kernel by $nd$ but none by $vc$ (unless NP $\subseteq$ coNP/poly), so polynomial kernels do not transfer along the poset the way FPT does. Exercise: map a problem, round 1 (handout; e-mail your map by Tue 10. 11.). Slides, Lecture notes |
| 6. 11. | Dean's day, no lecture |
| 13. 11. | Proving the hard side. Parameterized reductions and W[1]-hardness [PA 13.1]: Clique reduces to Multicolored Clique; List Coloring is W[1]-hard by $vc$, so on the parameter poset it is hard already at the bottom, unlike Chromatic Number. Partial Vertex Cover: W[1]-hard by the solution size $k$, FPT by the number $t$ of covered edges (results only, without proofs) [PA Thm 13.6, Ex. 5.11]. Lower bounds on running times: ETH, the basis of such bounds for 25 years, was refuted in October 2026. We use the Satisfiability Hypothesis of Stearns and Hunt instead; under it Clique has no $2^{k^{O(1)}} n^{O(k^{1-\varepsilon})}$ algorithm (proof by grouping clauses, as in [PA, proof of Thm 14.21]). Transferring such bounds along reductions, and the matching XP algorithm for List Coloring by $vc$. Slides, Lecture notes |
| 20. 11. | Plan: integer programming as a modeling hammer. ILP in fixed dimension (Lenstra) [PA 6.2]; Closest String by the number of strings; Capacitated Dominating Set by $nd$; $n$-fold IP and scheduling; ILP is W[1]-hard by the number of constraints; a vote on a new research question. |