Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revizePředchozí verze | |
| teaching:intro_par_alg2526 [2025/12/05 10:09] – Martin Koutecky | teaching:intro_par_alg2526 [2026/01/05 11:42] (aktuální) – [Material Covered] Jiří Fiala |
|---|
| | 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)$).| | | 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]]]**| | | 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 ]**| |
| /* | /* |
| |
