Uživatelské nástroje

Nástroje pro tento web


teaching:intro_par_alg2627

Toto je starší verze dokumentu!


Introduction to Parameterized Algorithms 26/27

Tutorial sessions

Tutorials are led by Martin Koreček, where you can find materials from the tutorial sessions and instructions on how to solve homework.

Material Covered

date what was said [source]
1. 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.).
6. 11. Dean's day, no lecture
13. 11. Plan: parameterized reductions and W[1]-hardness: Clique, Multicolored Clique, List Coloring by $vc$; lower bounds on running times, and what survives the October 2026 refutation of ETH.

Materials

teaching/intro_par_alg2627.1793391997.txt.gz · Poslední úprava: autor: Claude Cowork