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

This is an old revision of the document!


Algorithmique des graphes (24h, 3 ECTS)

Responsable: Reza Naserasr

Plan du cours et intervenants prévus pour 2018 – 2019

Pierre Aboulker (MTCF, ENS Paris-Ulm) September 10, 17, 24, October 1. Exam: October 8th

Reza Naserasr (CR CNRS IRIF) 12h, October 15, 22, 29, November 5 Exam: November 12

Presentation on either November 26, or December 3rd, or a choice in the class.

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

Objectifs

Ces dernières années plusieurs applications basées sur les graphes ont bouleversé notre environnement : Google avec son algorithme de graphe PageRank, Facebook avec son réseau social à base de graphe. L'explosion actuelle des réseaux sociaux et la disponibilité de gigantesques bases de données de graphes dans de nombreuses applications (par exemple de tous vos déplacements à l'aide d'applications de type Googlemaps, Ways, ...) pose le problème de l'apprentissage dans des bases de données de graphes.

Par ailleurs les modèles basés sur les graphes sont classiquement utilisés en recherche dans de nombreux domaines, tels que la chimie, la biologie, les réseaux de télécommunications ou encore les réseaux sociaux. Bien évidemment, les graphes constituent un des outils de modélisation les plus importants et les plus utilisés en informatique.

Cependant malgré la simplicité apparente de leur définition, les graphes capturent une large part de la complexité algorithmique. Ainsi, les classes de complexité telles P, NP et bien d'autres peuvent se définir comme l'ensemble des problèmes de graphes exprimables dans un certain fragment de la logique. Il est donc très important de comprendre en profondeur les différentes structures de graphes afin d'utiliser des modélisations pertinentes, c'est-à-dire des modélisations pour lesquelles les algorithmes de résolution sont efficaces.

Ce module a plusieurs objectifs principaux :

- Exposer les bases de la conception d'algorithmes efficaces sur les graphes;

- Etudier la structure des algorithmes gloutons sur les graphes

- Comprendre la complexité structurelle des graphes via des décompositions de graphes et les invariants de graphes associés;

- Comprendre comment appliquer ces algorithmes sur des très grands graphes (de la taile du graphe des amis de Facebook par exemple).

- Présenter quelques problèmes de recherche du domaine;

Description du cours

I - Graph Minor Theory and its algorithmic consequences - Pierre Aboulker - 4 lectures (12 hours) + 2 hours exam, from September 10th to October 8th

Graph minor theory is one of the deepest subjects in graph theory, the core of which was developed by Robertson and Seymour in a series of twenty five papers. In this course we will cover some of the central results in the theory, as well as its algorithmic consequences, including the following:

1. Short introduction to basic concepts of graph theory

2. Planar graphs

3. Treewidth and relatives (tree-decompositions, treewidth, excluding a planar graph, brambles...)

4. Applications of dynamic programming on graphs with bounded treewidth

5. Graph minor theory: Grid Minor Theorem, Kruskal's Theorem, Well Quasi Ordering...

6. Applications of graph minor theory on general algorithmic problems such as Rooted Disjoint Paths problem, Topological Minor Detection...

7. Applications of graph minor theory to Fixed Parameter Tractable (FPT) algorithms (FPT algorithm is a very important topic in algorithmic theory, roughly speaking it is a way to solve efficiently NP-Hard problem by cheating on the size of the input)

Supports for the class will be available on my webpage: Supports

II - Basic notions of graph theory. By Reza Naserasr - 4 lectures (October 15, 22, 29, November 5 Exam: November 12 )

Continuing from the first part of the cour we discuss some of main areas of graph theory such as, coloring and homomorphisms, flows, Hamiltonicty, etc. We present basic results on these subjects and show strong connection between these, seemingly independent, notions. We will have flexibility in the choice of results to be presented in the class and will adjust based on the interest of the students. A tentative plan is as follows:

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.

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

Cours conseillés:

Graph Mining, Algorithmique avancée, Complexité randomisée, Techniques en Cryptographie et Cryptanalyse, Algorithmique distribuée pour les réseaux, Algorithmique distribuée avec mémoire partagée, Optimisation, Théorie des calculs, Informatique quantique et applications, Algorithmes pour les graphes plongés.

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)

 
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