Instructors: Pierre Aboulker (ENS Paris-ULM) and Valia Mitsou (IRIF, Université Paris Cité)

Language of the course: English by default

Short Description of the Course: Parameterized complexity is a branch of computational complexity offering us tools in order to attack NP-hard problems, but also in order to solve more efficiently problems belonging in P. In parameterized complexity, we perform a more refined analysis of the algorithmic complexity of a problem: the running time is analyzed as a function of the input size as well as of one or more parameters. When the parameter is expected to be small, an algorithm polynomial in the input size but exponential in the parameter(s) is expected to be tractable, since the combinatorial explosion is confined to the (small) parameter(s).

In the first part of the course, we will discuss about the theory of parameterized complexity and define the different complexity classes; we will make an exposition of the main classical techniques that we use in the design of parameterized algorithms: kernelization, bounded search trees, iterative compression and color coding. We will also learn how to design lower-bounds and make the connection of parameterized and approximation algorithms (another branch of algorithms’ design for attacking NP-hardness). The second part of the course will be devoted to the study of probably the most successful and well-known structural parameter: the treewidth of a graph. We will first give a quick overview of the graph minor project that defined treewidth, essentially lead by Robertson and Seymour in a series of 23 articles published between 1993 and 2010. We will then see how to use this theory in order to design FPT algorithms. In particular, we will study the celebrated Courcelle’s Theorem and more advanced methods such as bidimentionality.

Why take this course:

• Parameterized Algorithms is already an established field of Theoretical Computer Science and FPT-related papers appear regularly every year in all major conferences (ex. FOCS, STOC, SODA, ICALP).
• Graph Minor Theory, which is taught in the second part of the course, is one of the deepest and most intriguing subjects in graph theory from both a structural and an algorithmic point of view. Courcelle’s theorem is a powerful tool with countless applications connecting logic, automata and graph theory.
• The notions covered in this course have a wide-spread use throughout theoretical computer science: students of MPRI who focus on algorithms and computational complexity are expected to come across these notions even when studying papers whose theme does not necessarily revolve around parameterized complexity.

Objectives of the course: This course offers an introduction to parameterized algorithms. It covers the most essential techniques for the design and analysis of parameterized algorithms. It also offers an introduction to treewidth, a central notion in algorithms as well as in structural graph theory.

Prerequisites: Familiarity with algorithms, computational complexity and graph theory.

Proposed Topics:

1. Introduction to Parameterized Complexity
2. Kernelization
3. Bounded-search trees
4. Iterative compression
5. Randomized techniques in parameterized algorithms (color coding)
6. Lower bounds: W-hierarchy, (Strong) Exponential Time Hypothesis, kernelization lower bounds
7. Dynamic Programming and Tree-Decompositions (Courcelle’s Theorem and well chosen examples)
8. Minors, Planar Graphs, Treewidth and Tree-Decompositions.
9. Well Quasi Ordering (Kruskal's theorem, well-quasi-ordering of graphs of bounded treewidth, Graph Minor Theorem)
10. Grid Minor Theorem and its application to parameterized algorithms
11. Other structural graph parameters (clique-width, tree-depth, …) as time permits

Schedule