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 yet to be scheduled.

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@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.

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 (tentative at places)

Date	Topic	Task statement	Solutions	Remarks
TBD	Reductions and exact exponential algorithms	PDF	Handwritten solutions
TBD	Kernelization	PDF	Handwritten solutions
TBD	Branch & Bound	PDF	Handwritten solutions
TBD	Randomized FPT algorithm for Longest Path problem via Color Coding	PDF	Included in the task statement
TBD	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.
TBD	Dynamic programming (over subsets)	PDF	None, sorry.
TBD	Treewidth: graph theory point of view	PDF	None, sorry.
TBD	Treewidth: dynamic programming over (nice) tree decompositions	PDF	None, sorry.
TBD	Courcelle's theorem: FPT algorithms for problems parameterized by treewidth without tears	Handwritten lecture notes	N/A
TBD	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
TBD	Integer programming and neighborhood diversity	PDF	PDF (even in LaTeX!)	Taught by Lluis Sabater Rojas.
TBD	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.