| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:intro_par_alg2425 [2024/10/09 16:42] – Martin Koutecky | teaching:intro_par_alg2425 [2024/12/17 22:45] (aktuální) – 17. 12. Martin Koutecky |
|---|
| ===== Tutorial sessions ===== | ===== Tutorial sessions ===== |
| |
| Tutorials are led by [[https://kam.mff.cuni.cz/~tung|Tung]]. | Tutorials are led by [[https://kam.mff.cuni.cz/~tung|Tung Anh Vu]]. |
| [[https://iuuk.mff.cuni.cz/~tung/teaching/fpt-winter2425/|Click here for the website of the tutorials]], 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. |
| | 1. 10. | Introduction to parameterized algorithms / complexity. **[PA 1]**| | | 1. 10. | Introduction to parameterized algorithms / complexity. **[PA 1]**| |
| | 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]**| | | 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. |//Plan: finish $2k$-vertex kernel for <typo fv:small-caps>Vertex Cover</typo> **[PA 2.5]**. 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]**//| | | 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]** | |
| /*| 19. 10. | Finishing kernels from last time. 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]** | |
| | 26. 10. | FPT algorithm for <typo fv:small-caps>Vertex Cover above LP</typo>, application: FPT algorithm for <typo fv:small-caps>Odd Cycle Transversal</typo> **[PA 3.4]**; | | | 5. 11. | //sport day - no class//| |
| | 2. 11. | **No class: [[https://www.mff.cuni.cz/en/internal-affairs/dean-s-day/2023|Dean's sport day]]**| | | 12. 11. | Dynamic programming and convolutions on <typo fv:small-caps>Set Cover</typo> and <typo fv:small-caps>Steiner Tree</typo> **[PA 6.1]**, PIE and <typo fv:small-caps>Hamiltonian Cycle</typo> **[PA 10.1.1]** | |
| | 9. 11. | 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]** | | | 19. 11. | Treewidth, nice tree decompositions, <typo fv:small-caps>Independent Set</typo> **[PA 7.2, 7.3.1]**| |
| | 16. 11. | Dynamic programming and convolutions on <typo fv:small-caps>Set Cover</typo> and <typo fv:small-caps>Steiner Tree</typo> **[PA 6.1]**, PIE and <typo fv:small-caps>Hamiltonian Cycle</typo> **[PA 10.1.1]** | | | 26. 11. | More Treewidth - grids, bidimensionality **[PA 7.7.1, 7.7.2 ]**| |
| | 23. 11. | Treewidth, nice tree decompositions, <typo fv:small-caps>Independent Set</typo> **[PA 7.2, 7.3.1]**| | | 3. 12. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**| |
| | 30. 11. | More Treewidth - FPT alg., MSO, grids **[PA 7.7.1, 7.7.2 ]**| | | 10. 12. | Neighborhood diversity: <typo fv:small-caps>Sum Coloring</typo> via $n$-fold IP, and as a convex IP in small dimension **[5M, Thm 2(a), 2(b)]**| |
| | 7. 12. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**| | | 17. 12. | Plan: Neighborhood diversity: Q&A on <typo fv:small-caps>Sum Coloring</typo> **[5M, Thm 2]**, <typo fv:small-caps>Capacitated Dominating Set</typo> **[5M, Thm 1]**; <typo fv:small-caps>Max $q$-Cut</typo> **[5M, Thm 3]**. [[https://www.geogebra.org/calculator/pfdttsng|Geogebra: $x \cdot y$ is obviously not convex.]]| |
| | 14. 12. | Neighborhood diversity: <typo fv:small-caps>Sum Coloring</typo> via $n$-fold IP, and as a convex IP in small dimension **[5M, Thm 2(a), 2(b)]**| | | 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)$).//| |
| | 21. 12. | Neighborhood diversity: finish <typo fv:small-caps>Sum Coloring</typo> **[5M, Thm 2]**, <typo fv:small-caps>Capacitated Dominating Set</typo> **[5M, Thm 1]**| | |
| | 4. 1. | Parameterized reductions, The W-hierarchy **[PA, 13.1, 13.2, 13.3]**| | |
| | 11. 1. | $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)$). |*/ | |
| |
| ===== Materials ===== | ===== Materials ===== |
