| Obě strany předchozí revizePředchozí verze | |
| teaching:intro_par_alg2526 [2025/11/10 15:10] – Martin Koutecky | teaching:intro_par_alg2526 [2025/12/05 10:09] (aktuální) – Martin Koutecky |
|---|
| | 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.| | | 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]]]**| |
| |
| /* | /* |
| |
| | 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]** | |
