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
Article presentation (50%) + Homework 1 (25%) + Homework 2 (25%)

Here are the guidelines for the article presentation

Here is the list of papers

Register your paper and book a slot for the oral presentation

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

Lectures

Lecture 1, 11/09: Bird's-eye view of the course. Gentle introduction to FPT and XP algorithms, or lack thereof, for some classic problems: Minimum Vertex Cover, Maximum Independent Set, Maximum Clique, k-Coloring.

Lecture 2, 14/09: Improved FPT algorithm for Min Vertex Cover in 1.46^k-time, enumeration of the at most 3^{n/3} maximal independent sets, k-SAT in better than 2^n-time. Notes.

Lecture 3, 18/09: Iterative compression, with the examples of Feedback Vertex Set and Odd Cycle Transversal. Notes.

Lecture 4, 21/09: Randomized algorithm for Feedback Vertex Set in 4^k-time, Color Coding (example of k-Path), and Random Separation (example of Bounded-Degree Subgraph Isomorphism). Notes, following sections 5.1, 5.2, 5.3, in param book.

Lecture 5, 25/09: Chromatic Coding for d-Cluster Edition, Measure and Conquer (example of Max Independent Set with a simple branching algorithm), Inclusion-Exclusion (example of Hamiltionian cycle). Notes, following sections 5.3. in param book, 6.1. in exact book, 10.1.1. in param book.

Lecture 6, 28/09: Kernels, sunflower lemma for Min Hitting Set, crown decomposition, 2k-kernel for Vertex Cover by Linear Programming (to be continued). Notes.

Lecture 7, 02/10: 2k-kernel for Vertex Cover by Linear Programming (end), linear kernel for Connected Vertex Cover in planar graphs, Turing kernels (example of Max Leaf Subtree). Notes.

Lecture 8, 05/10: Inclusion-Exclusion (example of k-Coloring), Ryser's formula, fast Zeta and Möbius transforms, fast cover product and subset convolution, application to counting the number of k-colorings of every induced subgraph in total O^*(2^n)-time. Notes.

Lecture 9, 09/10: Weighted Max Indepent Set (WMIS) on trees, path and tree decompositions, treewidth, pathwidth, nice decompositions, WMIS in time 2^w n^{O(1)} when given a nice tree decomposition of width w. Notes.

Lecture 10, 12/10: FPT reductions, simple examples, Multicolored k-Independent Set FPT-reduces to k-Dominating Set, W-hierarchy, Exponential Time Hypothesis (ETH), and Strong Exponential Time Hypothesis (SETH), a first consequence of ETH on Max Independent Set. Notes.

Lecture 11, 16/10: Kernel lower bounds: the theory. Notes.

Lecture 12, 19/10: Kernel lower bounds: examples of compositions. Max Independent Set in butterfly-free graphs, Disjoint Factors and Disjoint Paths, Min Vertex Cover. Notes.

Lecture 13, 23/10: Integer Linear Programming is FPT, cuts and separators. Notes.

Lecture 14, 02/11: Sparsification Lemma, more consequences of ETH and SETH, SETH implies ETH, ETH implies FPT is not W[1], matching ETH lower bounds in planar graphs, matching SETH lower bound for Max Independent Set parameterized by treewidth. Following Chapter 14 in param book.

Lecture 15, 06/11: Courcelle's theorem, treewidth lowerbound via brambles, example of grids, graph minors, finite obstruction set, existence of non-uniform FPT algorithms for minor-closed problems, grid minor theorem, bidimensionality, contraction minors.