====== Introduction to Parameterized Algorithms 26/27 ====== ===== Tutorial sessions ===== Tutorials are led by [[https://doslovaja.cz/ipa|Martin Koreček]], where you can find materials from the tutorial sessions and instructions on how to solve homework. ===== Material Covered ===== {{tablelayout?colwidth="100px,800px"&rowsHeaderSource=1&rowsVisible=100}} ^ date ^ what was said [source] ^ | 2. 10. | Introduction to parameterized algorithms / complexity. **[PA 1]** I mentioned [[https://dl.acm.org/doi/10.1145/3284176|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.). [[https://iuuk.mff.cuni.cz/~koutecky/paralg/paralg-2026-L1-slides.pdf|Slides]], [[https://iuuk.mff.cuni.cz/~koutecky/paralg2627-graph/app/#/page/Lecture%201%20%E2%80%93%20Colouring%20and%20structural%20parameters|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$. [[https://iuuk.mff.cuni.cz/~koutecky/paralg/paralg-2026-L2-slides.pdf|Slides]], [[https://iuuk.mff.cuni.cz/~koutecky/paralg2627-graph/app/#/page/Lecture%202%20%E2%80%93%20Proving%20the%20hard%20side|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.//| /* | 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]**. [[https://www.geogebra.org/calculator/pfdttsng|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)$).//| */ /* Vertex Cover in $\mathcal{O}^*(1.6181^k)$ and $\mathcal{O}^*(1.4656^k)$ time; */ ===== Materials ===== * **[LN]** [[https://iuuk.mff.cuni.cz/~koutecky/paralg2627-graph/|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 [[https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf| Parameterized Algorithms]]. /* * **[Ker]** is the book [[https://folk.uib.no/nmiff/BookKer/book_kernels.pdf| Kernelization]]. */ * **[ND]** [[https://www.lamsade.dauphine.fr/~mlampis/papers/metatheorems_journal.pdf|Algorithmic Meta-theorems for Restrictions of Treewidth]]: a paper which introduced $nd(G)$ and describes the coloring algorithm * **[NdCol]** [[https://rdcu.be/cUrsc|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]** [[https://www.sciencedirect.com/science/article/pii/S157252862030030X?ref=pdf_download&fr=RR-2&rr=8317fd563de2b333|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]** [[https://dl.acm.org/doi/10.1145/3421750|Polynomiality for Bin Packing with a Constant Number of Item Types]]