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]
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.

Materials

[LN] Lecture notes: definitions, theorems and proofs from the lectures, with links between them; updated after each lecture (from 30. 10. on).
[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