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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-29-1 [2018/11/06 15:28]
reza [Description du cours]
cours:c-2-29-1 [2019/09/06 17:45] (current)
reza [Description du cours]
Line 7: Line 7:
  
  
-Reza Naserasr (CR CNRS IRIF) 12h September 21, 28, October 5, 19 
  
-''There will be no course in October 12'' 
  
 +Pierre Aboulker (MTCF, ENS Paris-Ulm) September 10, 17, 24, October 1.
 +Exam: October 8th
  
-Pierre Charbit (MTCF, IRIF Paris-Diderot) October 26 November 2 
- 
-Pierluigi Crescenzi  (PR, IRIF Paris-Diderot) November 9, 16 
  
 +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. 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. 
  
  
Line 53: Line 51:
 ==== Description du cours ==== ==== 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:
  
-=== I - Basic notions of graph theory. By Reza Naserasr - 4 lectures (September 21, 28, October 5, 19)===+1. Short introduction to basic concepts of graph theory 
  
-Description: We introduce some of the basic theories of graph theory, such planarity and minors, coloring and homomorphisms, flows, Hamiltonicty, etc. +2Planar graphs
-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:+
  
-1Connection 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.+3Treewidth and relatives (tree-decompositions, treewidth, excluding a planar graph, brambles...)
  
 +4. Applications of dynamic programming on graphs with bounded treewidth 
  
-2Greedy algorithm for coloring Brookstheorem with an algorithmic proof, proving that 3-edge-coloring problem is NP-complete,+5Graph minor theory: Grid Minor TheoremKruskal's TheoremWell Quasi Ordering...
  
-3Vizing's theoremmaximum matchings and vertex cover, Menger theorem and its application to maximum matching in bipartite graphs, Tutte theorem, Marriage Hall theorem.+6Applications of graph minor theory on general algorithmic problems such as Rooted Disjoint Paths problemTopological Minor Detection...
  
-4Constraint Satisfaction Problems, homomorphisms of graphs and digraphdichotomy of CSP, integer programing vs linear programing, fractional chromatic number.+7Applications of graph minor theory to Fixed Parameter Tractable (FPT) algorithms (FPT algorithm is a very important topic in algorithmic theoryroughly speaking it is a way to solve efficiently NP-Hard problem by cheating on the size of the input)
  
-=== II - Introduction to Minors, TreeWidth and FPT algorithms - Pierre Charbit - 2 lectures October 26 November 2 ===+Supports for the class will be available on my webpage: 
 +[[https://www.di.ens.fr/~paboulker/|Supports]]
  
-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 
  
-[[http://www.irif.fr/~charbit/Enseignement/2018/MPRICharbitSlides.pdf|Slides of the 6 hours]] 
  
 +=== II - Basic notions of graph theory. By Reza Naserasr - 4 lectures (October 15, 22, 29, November 5 Exam: November 12 )===
  
-=== III - Spectral graph theory - Pierluigi Crescenzi - 2 lectures November 916===   +Continuing from the first part of the cour we discuss some of main areas of graph theory such ascoloring 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.
  
-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.+2. Greedy algorithm for coloring,  Brookstheorem 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. 
  
  
Line 89: Line 92:
 ==== Pré-requis ==== ==== Pré-requis ====
  
-Une bonne connaissance de l'algorithmique discrète et de la complexité des algorithmes ainsi que des algorithmes classiques sur les graphes +1. A basic knowledge on graph theory such as stable setclique numberchromatic number...  
-(plus courts cheminsarbre de poids minimumfermeture transitive).+ 
 +2. Classic graph algorithms such as shortest path or Ford-Fulkerson algorithm 
 + 
 +3. Good knowledge on algorithmic complexity theory 
 +  
 +4Dynamic programming
  
 Cours conseillés: Cours conseillés:
Line 97: Line 105:
  
 ==== Bibliographie ==== ==== Bibliographie ====
 +
 +[[http://www.esi2.us.es/~mbilbao/pdffiles/DiestelGT.pdf|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. Algorithmic graph theory and perfect graphs, M.C. Golumbic, Annals of Discrete Mathematics, 57, 2004.
Line 102: Line 114:
 Algorithm Design par J. Kleinberg et E. Tardos, Addison Welsey 2005. 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 ==== ==== É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)+P. Aboulker (MdC ENS Paris-UlmP. Charbit (MdC IRIF Université de Paris), Reza Naserasr (CNRSIRIF 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