6ème Cours Cours MPRI 2010–2011

6eme Cours Cours MPRI 2010{20116eme CoursCours MPRI 2010{2011Michel Habibhabib@liafa.jussieu.frhttp://www.liafa.jussieu.fr/ habib~Chevaleret, october 20106eme Cours Cours MPRI 2010{2011ScheduleTreewithGraph MinorsBig theorems on Graph MinorsOther width parametersCliquewidth6eme Cours Cours MPRI 2010{2011TreewithTree decompositionG = (V; E ) has a tree decomposition D = (S; T )S is a collection of subsets of V , T a tree whose vertices areelements of S such that :(0) The union of elements in S is V(i) 8e2 E ,9i2 I with e2 G (S ).i(ii) 8x2 V , the elements of S containing x form asubtree of T .De nitiontreewidth(G ) = Min (Max fjSj 1g)D S2S ii6eme Cours Cours MPRI 2010{2011Treewith6eme Cours Cours MPRI 2010{2011TreewithRecall of some Equivalences1. Treewidth(G ) = Min f!(H) 1gH triangulation of G2. Computing treewidth is NP-hard.6eme Cours Cours MPRI 2010{2011TreewithOther de nitions of trewidth in terms of cop-robber games, usinggraph grammars ....But it turns out that this parameter is a fundamental parameterfor graph theory.6eme Cours Cours MPRI 2010{2011TreewithSome examples1. G is a tree i treewidth(G ) = 12. treewidth(K ) = n 1n3. If G is a cycle then treewidth(G ) = 2. (It can be seen as twochains in parallel, i.e. a series-parallel graph)4. treewidth(K ) = min(n; m)n;m5.(G ) = min(n; m), the lower bound is hard ton;mobtain !6. treewidth(G ) (resp. pathwidth) measures the distance from Gto a tree (resp. to a ...