Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- teaching:intro_par_alg2526 [2025/10/20 13:15] – [Material Covered] Jiří Fiala
+++ teaching:intro_par_alg2526 [2026/01/05 11:42] (aktuální) – [Material Covered] Jiří Fiala
@@ Řádek 15: / Řádek 15: @@
 | 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]** |
-| 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 **[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. 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 ]**|
+/*
+| 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//|
 | 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]** |