Course Description

Most of the interesting graph-theoretic problems are NP-hard. Hence, unless P=NP, we do not expect polynomial time algorithms for these problems. Various paradigms have been developed to cope with this: approximation algorithms, randomized algorithms, average-case analysis, etc. However, if we insist on solving these problems exactly, then it leaves us with the following two options: exact exponential algorithms and fixed-parameter tractable (FPT) algorithms.

Classical complexity usually measures the running time of algorithm with respect to only the input length n. The relatively recent paradigm of parameterized complexity (introduced in the 90's) performs a more fine-grained analysis of the running time: the running time is expressed as a function of both n and of a parameter k that is often much smaller than n. The goal is to identify which parameters allow us to design fast algorithms for these NP-hard problems, i.e., algorithms of running time which is polynomial in n and the combinatorial explosion is handled only by the parameter k. Formally, a problem with input size n and parameter k is said to be fixed-parameter tractable (FPT) if it has an algorithm which runs in time f(k).poly(n) for some function f.

The field of parameterized algorithms and complexity has witnessed the development of several nice algorithmic insights and lower bound methodologies. The goal of this course is to give an introduction to the parameterized world, and equip you with an arsenal of algorithmic and lower bound techniques.

Book: We will (mostly) follow the book Parameterized Algorithms by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk and Saurabh.