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

Algorithmique des graphes (24h, 3 ECTS)

Responsable: Reza Naserasr

Plan du cours et intervenants prévus pour 2020 – 2021

Reza Naserasr (CR CNRS IRIF) 12h, Dec 7, 14, Jan 4, 11

Lecture Notes Here BBB Online Classroom

Pierre Charbit (MCF, IRIF) 12h, Jan 18,25 Feb 1, 8

Exam: to be decided.

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 - By Reza Naserasr - 4 lectures (Dec 7, 14, Jan 4,11 )

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. Applications of linear algebra and eigenvalue techniques

II - By Pierre Charbit - 4 lectures (Jan 18,25, Feb 1,8 )

Graph minor, treedwidth, ...

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