Lecturer: Mohammad Syed Meesum
This course will be about a framework used for solving NP-Hard problems.
Several paradigms exist for coping with NP-hardness: for example approximation
algorithms, randomized algorithms etc. Parameterized Complexity is a
relatively new paradigm for dealing with NP-Hard problems. Here the time
complexity of the algorithm depends not only on the input length but also on
an integer parameter "k" supplied along with the input. Usually the extra
integer k is the size of the required output. In some other cases, the input
parameter "k" captures some structural property of the input instance.
Increasing the parameter makes the problem harder. In this setting, the
running times of the algorithms are exponential only in the chosen parameter,
and are polynomial in the instance size. In other words when the parameter is
a fixed constant, the algorithm runs in polynomial time. For example it is
possible to design an algorithm running in linear time which answers yes if an
input graph has a vertex cover of size say 10, no otherwise. The main
advantage of this in terms of real life applications is that if the parameter
is small, then we get fast exact algorithms that work well in practice.
This course will start with some techniques for designing parameterized
algorithms. We would also explore the related notion of Kernelization, which
concerns itself with compressing input instances of NP-Hard problems using
polynomial time algorithms. We would also look at techniques for proving if
the problem does not admit a parameterized algorithm, assuming some popular
complexity theoretic beliefs.
Prerequisites:
Familiarity with basic notions of graph theory. Some understanding of the
notion of NP-Hardness.
We would be following the book freely available at <http://parameterized-
algorithms.mimuw.edu.pl/>
