MK's wiki

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== Introduction to Parameterized Algorithms 24/25 ======


===== Tutorial sessions =====

Tutorials are led by [[https://kam.mff.cuni.cz/~tung|Tung Anh Vu]].
[[https://iuuk.mff.cuni.cz/~tung/teaching/fpt-winter2425/|Click here for the website of the tutorials]], where
you can find materials from the tutorial sessions and instructions on how to solve homework.

===== Material Covered =====

{{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100&float=left}}
^ date ^ what was said [source] ^
| 1. 10. | Introduction to parameterized algorithms / complexity. **[PA 1]**|
| 8. 10. | Kernelization **[PA 2.1, 2.2.1, 2.3-intro, 2.3.1]**. Crown decomposition lemma proof was from **[Ker, Lemma 4.5]**|
| 15. 10. | FPT algorithm for <typo fv:small-caps>Vertex Cover above LP **[PA 3.4]**</typo>,|
| 22. 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]** |
| 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]** |
| 19. 11. | Treewidth, nice tree decompositions, <typo fv:small-caps>Independent Set</typo> **[PA 7.2, 7.3.1]**|
| 26. 11. | More Treewidth - grids, bidimensionality **[PA 7.7.1, 7.7.2 ]**|
| 3. 12. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**|
| 10. 12. | Neighborhood diversity: <typo fv:small-caps>Sum Coloring</typo> via $n$-fold IP, and as a convex IP in small dimension **[5M, Thm 2(a), 2(b)]**|
| 17. 12. | Plan: Neighborhood diversity: Q&A on <typo fv:small-caps>Sum Coloring</typo> **[5M, Thm 2]**, <typo fv:small-caps>Capacitated Dominating Set</typo> **[5M, Thm 1]**; <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.]]|
| 7. 1. | //Plan: $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)$).//|

===== Materials =====

  * **[PA]** is the book [[https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf| Parameterized Algorithms]].
  * **[Ker]** is the book [[https://folk.uib.no/nmiff/BookKer/book_kernels.pdf| Kernelization]].
  * **[ND]** [[https://www.lamsade.dauphine.fr/~mlampis/papers/metatheorems_journal.pdf|Algorithmic Meta-theorems for Restrictions of Treewidth]]: a paper which introduced $nd(G)$ and describes the coloring algorithm
  * **[NdCol]** [[https://rdcu.be/cUrsc|A note on coloring...]]: a paper by Martin which retells the coloring algorithm by Lampis and points out that it can be solved more efficiently
  * **[5M]** [[https://www.sciencedirect.com/science/article/pii/S157252862030030X?ref=pdf_download&fr=RR-2&rr=8317fd563de2b333|Integer programming in parameterized complexity: Five miniatures]] a comprehensive paper about various parameterized integer programming algorithms and their applications to problems on bounded-$nd$ graphs.
  * **[GR]** [[https://dl.acm.org/doi/10.1145/3421750|Polynomiality for Bin Packing with a Constant Number of Item Types]]