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

Algorithmique des graphes (24h, 3 ECTS)

Responsable: Reza Naserasr

Schedule of course for 2021 – 2022

Reza Naserasr (12h, Dec 10, 17, Jan 7, 14)

Lecture Notes Here

Matej Stehlik (12h, Jan 21, 28, Feb 4, 11)

Exam: to be decided.

Presentations: also to be decided.

All lectures will be given in English, but questions can be addressed in French.

General objectives

Graphs are fundamental tools for most areas of computer science.

Therefore there are two complimentary goal in this course:

The first goal is for all students attending to the course to learn tools and techniques on dealing with problems on graph theory. This would help in particular with stating your research problem using language of graph theory when needed.

The second goal of the course is to offer a deeper look for those student who are persuaded to continue graph theory as a main research career.

The number of particular subjects to be covered is too large, thus there will be flexibility on choosing the subject. That would depend on the common interest of students and teachers. A general list of subject, is given below, but the list itself could also be extended at request. If you are curios to learn a certain subject do not hesitate to write to the teachers of the course.

- Minor theory, planarity, etc.

- Various notions of coloring, such as proper vertex coloring, fractional coloring, edge-coloring, ...

- Important graph parameters: clique number, independence number, coloring number, Lavasz theta-function,...

- Graph homomorphisms and graph products,

- Algorithms, in particular: greedy algorithms, min-max theorems, linear programming ...

- Structured graphs: interval graph, permutation graphs, comparability graphs, perfect graphs, ...

- Eigenvalue techniques,

- Ramsey theory,

- Probabilistic methods and random graphs,

- Packing problems,

- Topological methods in graph theory,

- Graph limits

Plans of the course for 2021-2022 (subject to modification by request)

I - By Reza Naserasr - 4 lectures (Dec 10, 17, Jan 7, 14, Fridays at 12:45)

Lectures will cover some but not all of the following subjects.

1. Connection of the notions of planarity, vertex coloring, edge-coloring, hamiltonicity and nowhere-zero flows: we show how the four color theorem has given birth to all these theories.

2. Greedy algorithm for coloring, Brooks' theorem with an algorithmic proof, proving that 3-edge-coloring problem is NP-complete,

3. Vizing's theorem, maximum matchings and vertex cover, Menger theorem and its application to maximum matching in bipartite graphs, Tutte theorem, Marriage Hall theorem.

4. Constraint Satisfaction Problems, homomorphisms of graphs and digraph, dichotomy of CSP, integer programing vs linear programing, fractional chromatic number.

5. Ramsey theory,

6. Introduction random graphs

7. Applications of linear algebra and eigenvalue techniques

II - By Matej Stehlik - 4 lectures (Jan 21, 28, Feb 4, 11 Fridays at 12:45)

1. Chinese postman problem, T-joins and T-cuts

2. Travelling salesman problem

3. Introduction to polyhedral methods (matching and perfect matching polytope), fractional chromatic index

4. Topological methods (Kneser graphs, link it to the fractional chromatic number)

Pré-requis

1. A basic knowledge on graph theory such as stable set, clique number, chromatic number...

2. Classic graph algorithms such as shortest path or Ford-Fulkerson algorithm

3. Good knowledge on algorithmic complexity theory

4. Dynamic programming

Bibliographie

Graph Theory by Reinhard Diestel (see Chapter 12 for a brilliant presentation of Graph Minor Theory)

Graph Theory, A. Bondy, U.S.R. Murty, Springer-verlag, 2008.

Algorithmic graph theory and perfect graphs, M.C. Golumbic, Annals of Discrete Mathematics, 57, 2004.

Algorithm Design par J. Kleinberg et E. Tardos, Addison Welsey 2005.

Équipe pédagogique

P. Aboulker (MdC ENS Paris-Ulm) P. Charbit (MdC IRIF Université de Paris), Reza Naserasr (CNRS, IRIF Université de Paris), Matej Stehlik (Prof. IRIF Université de Paris)

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