| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:intro_par_alg2526 [2025/10/20 13:15] – [Material Covered] Jiří Fiala | teaching:intro_par_alg2526 [2025/11/10 15:10] (aktuální) – Martin Koutecky |
|---|
| | 6. 10. | Kernelization **[PA 2.1, 2.2.1, 2.3-intro, 2.3.1]**. Crown decomposition lemma proof was from **[Ker, Lemma 4.5]**| | | 6. 10. | Kernelization **[PA 2.1, 2.2.1, 2.3-intro, 2.3.1]**. Crown decomposition lemma proof was from **[Ker, Lemma 4.5]**| |
| | 13. 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]** | | | 13. 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]** | |
| | 20. 10. | FPT algorithms <typo fv:small-caps>Feedback Vertex Set</typo> in $\mathcal{O}^*((3k)^k)$ time and for <typo fv:small-caps>Vertex Cover above LP **[PA 3.4]**</typo>,| | | 20. 10. | FPT algorithms for <typo fv:small-caps>Feedback Vertex Set</typo> in $\mathcal{O}^*((3k)^k)$ time and for <typo fv:small-caps>Vertex Cover above LP in $\mathcal{O}^*(4^d)$ **[PA 3.3, 3.4]**</typo>| |
| /*| 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]** | | | 27. 10. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**| |
| | | 3. 11. | Neighborhood diversity: <typo fv:small-caps>Sum Coloring</typo> as a convex IP in small dimension, and later as $n$-fold IP **[5M, Thm 2(a), 2(b)]**; <typo fv:small-caps>Capacitated Dominating Set</typo> as small-dim IP with convex constraints. **[5M, Thm 1]**| |
| | | 10. 11. | $P/Q/R||C_{\max}$ via $n$-fold IP recap. How does the FPT $n$-fold IP algo work (birds-eye view). Borda-<typo fv:small-caps>Shift Bribery</typo> is FPT($m$) via $n$-fold IP.| |
| | |
| | /* |
| | |
| | | 17. 12. | Plan: Neighborhood diversity: Q&A on <typo fv:small-caps>Sum Coloring</typo> **[5M, Thm 2]**, ; <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.]]| |
| | |
| | | 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//| |
| | 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]** | | | 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]** | |
