
Instructors: Pierre Aboulker (ENS ParisULM) 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 NPhard 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 lowerbounds and make the connection of parameterized and approximation algorithms (another branch of algorithms’ design for attacking NPhardness). The second part of the course will be devoted to the study of probably the most successful and wellknown 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 FPTrelated 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 widespread 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:
Introduction to Parameterized Complexity
Kernelization
Boundedsearch trees
Iterative compression
Randomized techniques in parameterized algorithms (color coding)
Lower bounds: Whierarchy, (Strong) Exponential Time Hypothesis, kernelization lower bounds
Dynamic Programming and TreeDecompositions (Courcelle’s Theorem and well chosen examples)
Minors, Planar Graphs, Treewidth and TreeDecompositions.
Well Quasi Ordering (Kruskal's theorem, wellquasiordering of graphs of bounded treewidth, Graph Minor Theorem)
Grid Minor Theorem and its application to parameterized algorithms
Other structural graph parameters (cliquewidth, treedepth, ...) as time permits
Schedule
December 5 (Pierre A): Introduction to Parameterized Complexity, Boundedsearch trees, Kernelization, Randomized techniques in parameterized algorithms (color coding)
December 12 (Pierre A): Advanced kernelization algorithms (ILP, Crown decomposition, sun flower lemma), Iterative compression.
December 19 (Valia M): Whardness (chapter 13.113.3 and 13.6 from the textbook)
January 9 (Valia M): Introduction to treewidth (chapter 7.17.4 from the textbook, slides)
January 16: Midterm
January 23 (Pierre A): Graph Minor Theory
January 30 (Pierre A): Graph Minor theory
February 6 (Valia M): Advanced techniques on treewidth (chapter 11.2.1 from textbook, slides), Fine Grained Complexity (slides)
February 13 (Valia M): Finegrained complexity cont, Equivalent definitions for tw & pw (slides), Cliquewidth (slides)
February 20: Oral presentations
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 doublesided pages of notes. No other material is allowed.
