# Introduction to Parameterized Algorithms: Tutorial

Welcome to the website to the tutorial class of Introduction to Parameterized Algorithms (lecturers Jiri Fiala and Martin Koutecky). We are scheduled on Wednesday, 14:00 in room S4.

If you have a feeling that

• you don't understand something,
• you can't make a deadline,
• you don't have enough points for the credit,
• you don't know something you are supposed to know,
• I haven't told you something you are supposed to know,
• I should change or improve something,
• for some reason you are not able to obtain a perfect grade from this course
write me (tung@kam.mff.cuni.cz) before it's too late. We'll meet (in cyberspace if needed) and try to resolve it somehow.

## How to obtain credit?

You will get credit for solving homework. There will be a homework set every week. You need 66 % of the points to obtain the credit.

Submit your homework solutions in the Postal Owl. The enrollment token is `a0b275bb74d6`.

I encourage discussing homework solutions among yourselves. However, make sure you create the submitted solution on your own.

## Tutorial content

1. : Reminder of basic complexity.
2. : Basic FPT stuff.
3. : Kernelization, half-integrality of vertex cover.
4. : Branch and bound.
5. : Branch and bound above guarantee.
6. : More kernelization. Sketch of bounds against polynomial kernels..
7. : Q&A of Odd Cycle Transversal via iterative compression.
8. : Iterative compression.
9. : Dynamic programming over subsets & inclusion-exclusion principle.
10. : Structural properties of treewidth.
11. : Scheduling meets integer programming, neighborhood diversity.
12. : n-fold integer programming and its applications.
13. : Dynamic programming on tree decompositions, bidimensionality.
14. : Color coding, W[1]-hardness.