Uživatelské nástroje

Nástroje pro tento web


teaching:intro_par_alg2627

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
Následující verze
Předchozí verze
teaching:intro_par_alg2627 [2026/11/13 18:03] – 13.11 lecture: what was covered, slides, lecture notes; 20.11 plan Claude Coworkteaching:intro_par_alg2627 [2026/11/14 20:08] (aktuální) – 20.11 plan: IP (lecture order changed) Claude Cowork
Řádek 17: Řádek 17:
 | 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. | Proving the hard side. Your maps from round 1. 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 **[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]]| +| 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: elections and the bribery map. Voting rules; <typo fv:small-caps>Kemeny Score</typo> in $\mathcal{O}^*(2^m)$ time by dynamic programming over subsets; bribery problems, and how their many variants form a map, like the parameter poset; which variant is worth studying.//|+| 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]** |
teaching/intro_par_alg2627.1794593006.txt.gz · Poslední úprava: autor: Claude Cowork