| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:intro_par_alg2627 [2026/10/16 17:23] – [Material Covered] Jiří Fiala | teaching:intro_par_alg2627 [2026/11/14 20:08] (aktuální) – 20.11 plan: IP (lecture order changed) Claude Cowork |
|---|
| {{tablelayout?colwidth="100px,800px"&rowsHeaderSource=1&rowsVisible=100}} | {{tablelayout?colwidth="100px,800px"&rowsHeaderSource=1&rowsVisible=100}} |
| ^ date ^ what was said [source] ^ | ^ date ^ what was said [source] ^ |
| | 1. 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]]| | | 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, <typo fv:small-caps>Vertex Cover</typo> kernel of size $3k$ via crown decomposition **[PA 2.1, 2.2.1, 2.3-intro, 2.3.1]**| | | 9. 10. | Kernelization, <typo fv:small-caps>Vertex Cover</typo> kernel of size $3k$ via crown decomposition **[PA 2.1, 2.2.1, 2.3-intro, 2.3.1]**| |
| | 16. 10. | Kernel for <typo fv:small-caps>Vertex Cover</typo> by LP **[PA 2.5]**, FPT algorithm for <typo fv:small-caps>Vertex Cover above LP</typo> **[PA 3.4]**,| | | 16. 10. | Kernel for <typo fv:small-caps>Vertex Cover</typo> by LP **[PA 2.5]**, FPT algorithm for <typo fv:small-caps>Vertex Cover above LP</typo> **[PA 3.4]**| |
| | | 23. 10. | Bounded Search Trees: <typo fv:small-caps>Feedback Vertex Set</typo> in $\mathcal{O}^*( (3k)^k)$ time; <typo fv:small-caps>Closest String</typo> in $\mathcal{O}^*(d^d)$ time **[PA 3.3, 3.5]**| |
| | | 30. 10. | <typo fv:small-caps>Chromatic Number</typo> under structural parameters. Since <typo fv:small-caps>3-Coloring</typo> 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 <typo fv:small-caps>Chromatic Number</typo> by $vc$, by $td$ (branching along an elimination forest, polynomial space) and by $nd$ (ILP in fixed dimension) **[ND, NdCol]**. Kernels: <typo fv:small-caps>Chromatic Number</typo> 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]**: <typo fv:small-caps>Clique</typo> reduces to <typo fv:small-caps>Multicolored Clique</typo>; <typo fv:small-caps>List Coloring</typo> is W[1]-hard by $vc$, so on the parameter poset it is hard already at the bottom, unlike <typo fv:small-caps>Chromatic Number</typo>. <typo fv:small-caps>Partial Vertex Cover</typo>: 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 <typo fv:small-caps>Clique</typo> 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 <typo fv:small-caps>List Coloring</typo> 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]**; <typo fv:small-caps>Closest String</typo> by the number of strings; <typo fv:small-caps>Capacitated Dominating Set</typo> by $nd$; $n$-fold IP and scheduling; ILP is W[1]-hard by the number of constraints; a vote on a new research question.//| |
| /* | /* |
| | 22. 10. | Bounded Search Trees: <typo fv:small-caps>Vertex Cover</typo> in $\mathcal{O}^*(1.6181^k)$ and $\mathcal{O}^*(1.4656^k)$ time; <typo fv:small-caps>Closest String</typo> in $\mathcal{O}^*(d^d)$ time **[PA 3.1, 3.5]** | | |
| | 29. 10. | Iterative Compression for <typo fv:small-caps>Vertex Cover</typo>, <typo fv:small-caps>Feedback Vertex Set</typo> and <typo fv:small-caps>Odd Cycle Transversal</typo>, **[PA 4.1, 4.3.1, 4.4]** | | | 29. 10. | Iterative Compression for <typo fv:small-caps>Vertex Cover</typo>, <typo fv:small-caps>Feedback Vertex Set</typo> and <typo fv:small-caps>Odd Cycle Transversal</typo>, **[PA 4.1, 4.3.1, 4.4]** | |
| | 5. 11. | //sport day - no class//| | | 5. 11. | //sport day - no class//| |
| | 7. 1. | //Plan: $P||C_{\max}$ is FPT($d$) if $p_{\max}$ unary bounded, using the algorithm of Goemans-Rothvoss **[GR]**. Another application: <typo fv:small-caps>Equitable Coloring</typo> is FPT($nd(G)$).//| | | 7. 1. | //Plan: $P||C_{\max}$ is FPT($d$) if $p_{\max}$ unary bounded, using the algorithm of Goemans-Rothvoss **[GR]**. Another application: <typo fv:small-caps>Equitable Coloring</typo> is FPT($nd(G)$).//| |
| */ | */ |
| | |
| | |
| | /* <typo fv:small-caps>Vertex Cover</typo> in $\mathcal{O}^*(1.6181^k)$ and $\mathcal{O}^*(1.4656^k)$ time; */ |
| |
| ===== Materials ===== | ===== 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]]. | * **[PA]** is the book [[https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf| Parameterized Algorithms]]. |
| /* | /* |