Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Parameterized Algorithms
(2023/2024, 24h, 3 ECTS)

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


  1. December 5 (Pierre A): Introduction to Parameterized Complexity, Bounded-search trees, Kernelization, Randomized techniques in parameterized algorithms (color coding)
  2. December 12 (Pierre A): Advanced kernelization algorithms (ILP, Crown decomposition, sun flower lemma), Iterative compression.
  3. December 19 (Valia M): W-hardness (chapter 13.1-13.3 and 13.6 from the textbook)
  4. January 9 (Valia M): Introduction to treewidth (chapter 7.1-7.4 from the textbook, slides)
  5. January 16: Midterm
  6. January 23 (Pierre A): Graph Minor Theory
  7. January 30 (Pierre A): Graph Minor theory
  8. February 6 (Valia M): Advanced techniques on treewidth (chapter 11.2.1 from textbook, slides), Fine Grained Complexity (slides)
  9. February 13 (Valia M): Fine-grained complexity cont, Equivalent definitions for tw & pw (slides), Clique-width (slides)
  10. February 20: Oral presentations
  11. February 27: Final exam

Textbooks and other material:

Exams: There will be a midterm exam on January 16th (40% of the grade) and a final exam on February 27th (60% of the grade). There will also be an optional presentation of a research paper on February 20th.

Here is a link to the midterm exam and links to the solutions for part A and part B

The exam on February 27th will start at 12:45pm (duration 3 hours). It will cover all 8 lectures of the course. You are allowed to prepare 3 double-sided pages of notes. No other material is allowed.

Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA