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

2023-10-04: Reminder of basic complexity.
2023-10-11: Basic FPT stuff.
2023-10-18: Kernelization, half-integrality of vertex cover.
2023-10-25: Branch and bound.
2023-11-01: Branch and bound above guarantee.
2023-11-08: More kernelization. Sketch of bounds against polynomial kernels..
2023-11-15: Q&A of Odd Cycle Transversal via iterative compression.
2023-11-22: Iterative compression.
2023-11-29: Dynamic programming over subsets & inclusion-exclusion principle.
2023-12-06: Structural properties of treewidth.
2023-12-13: Scheduling meets integer programming, neighborhood diversity.
2023-12-20: n-fold integer programming and its applications.
2023-01-03: Dynamic programming on tree decompositions, bidimensionality.
2023-01-10: Color coding, W[1]-hardness.