| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:intro_par_alg2526 [2025/11/04 22:36] – [Material Covered] Martin Koutecky | teaching:intro_par_alg2526 [2026/01/05 11:42] (aktuální) – [Material Covered] Jiří Fiala |
|---|
| | 27. 10. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**| | | 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]**| | | 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. 11. | [[https://en.wikipedia.org/wiki/International_Students%27_Day|International Student's Day]] | |
| | | 24. 11. | Neighborhood diversity: <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.]] $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)$).| |
| | | 1. 12. | Parameterized Hardness: W[1]-hard problems (<typo fv:small-caps>Clique</typo>), parameterized reductions from <typo fv:small-caps>Clique</typo> to <typo fv:small-caps>Independent Set</typo>, to <typo fv:small-caps>Clique</typo> on regular graphs, to <typo fv:small-caps>Partial Vertex Cover</typo> (parameterized by size), to <typo fv:small-caps>Multicolored Clique</typo> **[PA 13.1]**. A reduction from <typo fv:small-caps>Unary Bin Packing</typo> parameterized by $k=\#$bins to uniform <typo fv:small-caps>$n$-fold IP</typo> with small $r,s, \|D\|_\infty$ but unary $\|A\|_\infty$. **[[https://dl.acm.org/doi/10.1145/3396855|[Lemma 5.1]]]**| |
| | | 8. 12. | Treewidth, nice tree decompositions, <typo fv:small-caps>Independent Set</typo> **[PA 7.2, 7.3.1]**| |
| | | 15. 1. | //cancelled//| |
| | | 5. 1. | More Treewidth - grids, bidimensionality **[PA 7.7.1, 7.7.2 ]**| |
| | /* |
| |
| |
| /* | |
| |
| | 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]** | | | 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]** | |
