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

write me ( 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.