Parameterized and exact algorithms
Lecturers: Édouard Bonnet and Rémi Watrigant

We present algorithmic tools to optimally solve NP-hard problems faster than the brute-force approach. We introduce parameterized algorithms and complexity. The focus is on techniques and how they exploit the input structure to serve both parameterized and moderately exponential/subexponential algorithms. We also highlight complexity-theoretic assumptions and how they often permit to complement the known algorithms by essentially matching conditional lower bounds.

Tentative Outline

Article presentation

Familiarity with basic notions on algorithms, graphs, and complexity theory

Parameterized Algorithms by Cygan et al.
Exact Algorithms by Fomin and Kratsch
Kernelization by Fomin et al.