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/03 11:16] – testing table width Claude Coworkteaching:intro_par_alg2627 [2026/11/14 20:08] (aktuální) – 20.11 plan: IP (lecture order changed) Claude Cowork
Řádek 4: Řádek 4:
 ===== Tutorial sessions ===== ===== Tutorial sessions =====
  
-Tutorials are led by [[https://kam.mff.cuni.cz/~tung|Tung Anh Vu]]. +Tutorials are led by [[https://doslovaja.cz/ipa|Martin Koreček]], where
-[[https://iuuk.mff.cuni.cz/~tung/teaching/fpt-winter2425/|Click here for the website of the tutorials]], where+
 you can find materials from the tutorial sessions and instructions on how to solve homework. you can find materials from the tutorial sessions and instructions on how to solve homework.
  
Řádek 12: Řá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]**|+| 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]**| 
 +| 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.//|
 /* /*
-| 8. 10. | Kernelization **[PA 2.1, 2.2.1, 2.3-intro, 2.3.1]**. Crown decomposition lemma proof was from **[Ker, Lemma 4.5]**| 
-| 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 27: Řá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]].
 +/*
   * **[Ker]** is the book [[https://folk.uib.no/nmiff/BookKer/book_kernels.pdf| Kernelization]].   * **[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   * **[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   * **[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
teaching/intro_par_alg2627.1791026219.txt.gz · Poslední úprava: autor: Claude Cowork