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

write me (tung@iuuk.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 two weeks. You need 66 % of the points to obtain the credit. This semester, you need at least 65 points to get 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

Date Topic Task statement Solutions Remarks
Reminber of basic complexity PDF Handwritten solutions
Kernelization PDF Handwritten solutions
Branch & Bound PDF Handwritten solutions
Randomized FPT algorithm for Longest Path problem via Color Coding PDF Included in the task statement
Iterative compression PDF Handwritten solutions The algorithm for Disjoint Split Vertex Deletion is described in Lemma 3 in this paper. The algorithm they get is cubic. The algorithm I describe in the solutions is quintic.
Dynamic programming (over subsets) PDF None, sorry.
Treewidth: graph theory point of view PDF None, sorry.
Treewidth: dynamic programming over (nice) tree decompositions PDF None, sorry.
Courcelle's theorem: FPT algorithms for problems parameterized by treewidth without tears Handwritten lecture notes N/A
Crash course on Hardness results in the parameterized world. I.e. how to show that a problem does not have an FPT algorithm or a polynomial kernel. Handwritten lecture notes N/A
Integer programming and neighborhood diversity PDF PDF (even in LaTeX!) Taught by Lluis Sabater Rojas.
FPT algorithm for Closest String problem via integer programming. Subexponential algorithm for Vertex Cover in planar graphs via bidimensionality. PDF PDF (even in LaTeX!)

Taught by Lluis Sabater Rojas.

There is an error in the solutions when dealing with duplicate column types. Consider a column type. For each its instance (meaning a copy in the input matrix) we can use a different character in the solution. Thus our variable needs to consider how many copies of an instance receive a certain character as the output. As a sanity check, there are l times more variables than what I describe in the solutions. This should also be reflected in the objective function.