teaching:intro_par_alg2627
Toto je starší verze dokumentu!
Introduction to Parameterized Algorithms 26/27
Tutorial sessions
Tutorials are led by Martin Koreček, where you can find materials from the tutorial sessions and instructions on how to solve homework.
Material Covered
| date | what was said [source] |
|---|---|
| 1. 10. | Introduction to parameterized algorithms / complexity. [PA 1] I mentioned this connection between parameterized and exponential algorithms |
| 9. 10. | Kernelization [PA 2.1, 2.2.1, 2.3-intro, 2.3.1], Crown decomposition| /* | 15. 10. | FPT algorithm for Vertex Cover above LP [PA 3.4],| | 22. 10. | Bounded Search Trees: Vertex Cover in $\mathcal{O}^*(1.6181^k)$ and $\mathcal{O}^*(1.4656^k)$ time; Closest String in $\mathcal{O}^*(d^d)$ time **[PA 3.1, 3.5] |
| 29. 10. | Iterative Compression for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal, [PA 4.1, 4.3.1, 4.4] |
| 5. 11. | sport day - no class |
| 12. 11. | Dynamic programming and convolutions on Set Cover and Steiner Tree [PA 6.1], PIE and Hamiltonian Cycle [PA 10.1.1] |
| 19. 11. | Treewidth, nice tree decompositions, Independent Set [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 Coloring on graphs of bounded $nd(G)$. [ND, NdCol, 5M] |
| 10. 12. | Neighborhood diversity: Sum Coloring 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 Sum Coloring [5M, Thm 2], Capacitated Dominating Set [5M, Thm 1]; Max $q$-Cut [5M, Thm 3]. 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: Equitable Coloring is FPT($nd(G)$). |
*/
Materials
- [PA] is the book Parameterized Algorithms.
- [Ker] is the book Kernelization.
- [ND] Algorithmic Meta-theorems for Restrictions of Treewidth: a paper which introduced $nd(G)$ and describes the coloring algorithm
- [NdCol] 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] 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.
teaching/intro_par_alg2627.1791571217.txt.gz · Poslední úprava: autor: Jiří Fiala
