| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:intro_par_alg2627 [2026/11/02 19:42] – Link the lecture notes [LN] Claude Cowork | teaching:intro_par_alg2627 [2026/11/14 20:08] (aktuální) – 20.11 plan: IP (lecture order changed) Claude Cowork |
|---|
| | 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]]| | | 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//| | | 6. 11. | //Dean's day, no lecture//| |
| | 13. 11. | //Plan: parameterized reductions and W[1]-hardness: <typo fv:small-caps>Clique</typo>, <typo fv:small-caps>Multicolored Clique</typo>, <typo fv:small-caps>List Coloring</typo> by $vc$; lower bounds on running times, and what survives the October 2026 refutation of ETH.//| | | 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.//| |
| /* | /* |
| | 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]** | |