Parameterized Complexity and Fixed-Parameter Algorithms

Fixed-parameter algorithms provide a powerful approach for efficiently solving many NP-hard problems by exploiting structural aspects of problem instances in terms of a problem parameter. The goal of this course is to provide an overview of the main advances and techniques used for the development of fixed-parameter algorithms and to introduce students to the rapidly developing paradigm of parameterized complexity. After finishing the course, students should be able to understand recent scientific advances in the field, develop basic kernelization and fixed-parameter algorithms for various problems, and also have access to techniques which can rule out the existence of such algorithms under certain conditions.