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