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/10/09 18:42] – [Materials] Jiří Fialateaching:intro_par_alg2627 [2026/11/14 20:08] (aktuální) – 20.11 plan: IP (lecture order changed) Claude Cowork
Řádek 11: Řádek 11:
 {{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 **[PA 2.1, 2.2.1, 2.3-intro, 2.3.1]**, Crown decomposition|+| 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]**| 
 +| 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.//|
 /* /*
-| 15. 10. | FPT algorithm for <typo fv:small-caps>Vertex Cover above LP **[PA 3.4]**</typo>,| 
-| 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//|
Řádek 26: Řádek 30:
 | 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]].
 /* /*
teaching/intro_par_alg2627.1791571322.txt.gz · Poslední úprava: autor: Jiří Fiala