Introduction to Parameterized Algorithms: Tutorial

Welcome to the website to the tutorial class of Introduction to Parameterized Algorithms (lecturers Jiri Fiala and Martin Koutecky).

The lecture's website is here.

We are scheduled on Tuesdays at 17:20 in room S3.

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

How to obtain credit?

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

Submit your homework solutions in the Postal Owl. The enrollment token is 2c188fc0b735.

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

Using computer algebra systems is fully allowed and encouraged in your solutions. Ideally, please send a link/certificate in the complexity sense to how you used it for solving the problem. So e.g. a Wolfram alpha URL that includes your expression.

Tutorial content

1. 2024-10-01: Reminder of basic complexity. Solutions.
2. 2024-10-08: Kernelization. Solutions.
3. 2024-10-15: Branch and bound. Solutions.
4. 2024-10-22: Longest path via color coding (solutions included).
5. 2024-10-29: Iterative compression. Solutions.
6. 2024-11-12: Dynamic programming (over subsets).
7. 2024-11-19: Treewidth: graph theory.