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

Textbooks and other material:

• Support for the courses given by Pierre Aboulker can be found here: https://www.di.ens.fr/~paboulker/
• The slides for the lectures given by Valia Mitsou can be found here: https://www.irif.fr/~vmitsou/parameterized24-25/
• Parameterized Algorithms, by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk and Saurabh: a textbook on parameterized algorithms covering most of the subjects of this course. https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf
• Graph Theory, by Diestel: a textbook on graph theory. Chapter 12 can be used as companion notes for the part on graph minor theory. http://www.esi2.us.es/~mbilbao/pdffiles/DiestelGT.pdf
• Seymour explain the origin of treewidth on StackExchange! https://cstheory.stackexchange.com/questions/5018/the-origin-of-the-notion-of-treewidth

Schedule

1. December 11 (Pierre A): Introduction to Parameterized Complexity, Bounded-search trees, Kernelization, Randomized techniques in parameterized algorithms (color coding)
2. December 18 (Pierre A): Advanced kernelization algorithms (ILP, Crown decomposition, sun flower lemma), Iterative compression.
3. January 8 (Valia M): W-hardness (chapter 13.1-13.3 and 13.6 from the textbook)
4. January 15 (Valia M): Introduction to treewidth (chapter 7.1-7.4 from the textbook, slides)
5. January 22: Midterm
6. January 29 (Pierre A):
7. February 5 (Pierre A):
8. February 12 (Valia M):
9. February 19 (Valia M):
10. February 26: Oral presentations
11. March 5: Final exam

Announcements

[17/1] The midterm exam is on Wednesday 22/1 during regular class time and it's two-hours long. It's closed-book but we will allow 4 two-sided pages of handwritten notes. It will be based on the first four lectures (introductory algorithmic techniques, W-hardness, and intro to treewidth).

  Chapters from the textbook:
* Chapter 1. 
* Chapter 2: 2.1, 2.2.1, 2.2.2, 2.3.1, 2.5, 2.6
* Chapter 3: 3.1, 3.2, 3.3, 3.4
* Chapter 4: 4.1, 4.3.1
* Chapter 5: 5.2
* Chapter 7: 7.1, 7.2, 7.3.1, 7.3.2, 7.4
* Chapter 13: 13.1, 13.2 (until page 432), 13.3 and Thm 13.30 from 13.6