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 2018 – 2019

Reza Naserasr (CR CNRS IRIF) 12h September 21, 28, October 5, 19

There will be no course in October 12

Pierre Charbit (MTCF, IRIF Paris-Diderot) October 26 November 2

Pierluigi Crescenzi (PR, IRIF Paris-Diderot) November 9, 16

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

There will one exam for the full course, and we will have a presentation day if there are enough volunteers. Dates for both to be determined after discussion in the class.

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 - Basic notions of graph theory. By Reza Naserasr - 4 lectures (September 21, 28, October 5, 19)

Description: We introduce some of the basic theories of graph theory, such planarity and minors, coloring and homomorphisms, flows, Hamiltonicty, etc. We present basic result 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 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.

II - Introduction to Minors, TreeWidth and FPT algorithms - Pierre Charbit - 2 lectures October 26 November 2

1. Rooted disjoint path problem. Link with topological minor and minor detection and minor closed classes membership. cStatement of Robertson and Seymour Theorem. Definition of TreeWidth

2. TreeWidh and Separators, Treewidth and Planar Graphs, Algorithms for treewidth and bounded treewidth graphs

Slides of the 6 hours

III - Spectral graph theory - Pierluigi Crescenzi - 2 lectures November 9, 16

1. The Laplacian matrix, its eigenvalues and the connection with some combinatorial properties of a graph.

2. Cheeger's inequalities and the Fiedler's algorithm.

Pré-requis

Une bonne connaissance de l'algorithmique discrète et de la complexité des algorithmes ainsi que des algorithmes classiques sur les graphes (plus courts chemins, arbre de poids minimum, fermeture transitive).

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

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.

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

Équipe pédagogique

P. Charbit (MC Paris 7), Pierluigi Crescenzi (PR Paris 7) Michel Habib (Pr Paris 7), Fabien de Montgolfier (MC Paris 7), Reza Naserasr (CNRS IRIF)

 
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