29th European Summer School in Logic, Language, and Information
University of Toulouse (France), 17-28 July, 2017

Parameterized Complexity and Fixed-Parameter Algorithms

Robert Ganian

Logic and Computation (Introductory)

Second week, from 14:00 to 15:30


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.