The course will be given by Syed Mohammad Meesum.
The course will be providing an introduction to the field of Parameterized Complexity.
We will begin with stating the basic definitions and goals of the subject.
I particular we would be focussing on the following.
1. Kernelization -- compressing input instances.
2. Branching and bounded-depth search trees.
3. Iterative Compression — a general template for solving some graph deletion problems.
4. Color Coding / Randomized methods — application to longest path etc.
5. Parameterization Above Guarantee, LP based methods.
6. W-hardness — when is a problem not fixed parameter tractable.
By the end of the course, students would be expected to read papers and present them to the class.
Requirements: basic probability theory, basic complexity theory (NP-completeness).
Reading: https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf
