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. 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.

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

Tentative Outline

• Bounded search tree: applications to fixed-parameter tractable (FPT) and moderately exponential algorithms, and enumeration, the case of Vertex Cover and Independent Set
• Kernels: reduction rules, crown decomposition, sun-flower lemma, case of Vertex Cover, d-Hitting Set, and Feedback Vertex Set (expansion lemma and Gallai's theorem)
• Further FPT techniques: iterative compression, color coding, random separation, derandomisation, representative sets and matroids
• Treewidth - structure: planar graphs, balanced separators, grid minor theorems, other graph widths
• Treewidth - algorithms: computing treewidth, Courcelle's Theorem, dynamic programming over tree decompositions, subexponential algorithms on planar graphs, bidimensionality
• Measure and Conquer: applications for exact and parameterized problems, case of Dominating Set
• Hardness: W-hierarchy, parameterized reductions, lower bounds under ETH and SETH for classical and parameterized problems, gadgetry
• Kernel lower bounds: distillation and composition for OR and AND, example with natural and structural parameters
• Algorithmic/complexity tools for geometric problems: shifting technique, local search, small separators in the input or the output, links with approximation, Grid Tiling
• Algebraic techniques: inclusion-exclusion, fast Zeta and Möbius transforms, fast subset convolution, case of Coloring and k-Path

Evaluation
Exam and article presentation

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