cours:c-2-29-1 [2018/11/06 15:28] reza [Description du cours] |
cours:c-2-29-1 [2019/10/15 08:35] (current) reza [Description du cours] |

| | | |

| | | |

- | ==== Plan du cours et intervenants prévus pour **2018 **-- **2019 **==== | + | ==== Plan du cours et intervenants prévus pour **2019 **-- **2020 **==== |

| | | |

| | | |

- | 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. | |

| | | |

| | | |

| ==== 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**.** ** | + | **2**. **Planar 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:** | + | |

| | | |

- | **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**. | + | **3**. **Treewidth **and **relatives (tree**-**decompositions, treewidth, excluding a planar graph, brambles..**.**)** |

| | | |

| + | 4. Applications of dynamic programming on graphs with bounded treewidth |

| | | |

- | **2**. **Greedy algorithm for coloring**, ** Brooks**' **theorem with an algorithmic proof, proving that 3-edge-coloring problem is NP-complete**, | + | **5**. **Graph minor theory: Grid Minor Theorem**, **Kruskal**'**s Theorem**, **Well Quasi Ordering...** |

| | | |

- | **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**. | + | **6**. **Applications of graph minor theory on general algorithmic problems such as Rooted Disjoint Paths problem**, **Topological Minor Detection..**. |

| | | |

- | **4**. **Constraint Satisfaction Problems, homomorphisms **of **graphs and digraph**, **dichotomy **of **CSP, integer programing vs linear programing, fractional chromatic number.** | + | **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)** |

| | | |

- | **=== 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 9**, **16=== ** | + | **Continuing from the first part of the cours 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. |

| | | |

- | 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, 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 ==== | | ==== 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 set**, **clique number**, **chromatic number... ** |

- | **(plus courts chemins**, **arbre de poids minimum**, **fermeture transitive)**. | + | ** ** |

| + | **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: | | Cours conseillés: |

| | | |

| ==== 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. |

| 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**-Ulm**) **P. Charbit **(**MdC IRIF Université **de Paris), Reza Naserasr (CNRS**, **IRIF **Université de Paris**) |