6ème Cours   Cours MPRI 2010–2011
51 Pages

6ème Cours Cours MPRI 2010–2011


Downloading requires you to have access to the YouScribe library
Learn all about the services we offer


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



Published by
Reads 29
Language English
Cours MPRI 2010–2011
6e`meCours Cours MPRI 2010–2011
Michel Habib habib@liafa.jussieu.fr http://www.liafa.jussieu.fr/~habib
Chevaleret, october 2010
Graph Minors
Big theorems on Graph Minors
Other width parameters
Tree decomposition
G= (V,E) has a tree decompositionD= (S,T) Sis a collection of subsets ofV,Ta tree whose vertices are elements ofSsuch that :
(0)The union of elements in S is V (i)eE,iIwitheG(Si). (ii)xV, the elements of S containingxform a subtree ofT.
Definition treewidth(G) =MinD(MaxSiS{|Si| −1})
1. 2.
of some Equivalences
Treewidth(G) =MinH triangulation of Computing treewidth is NP-hard.
6`emeCoursCoursMPRI20102011 Treewith
Other definitions of trewidth in terms of cop-robber games, using graph grammars .... But it turns out that this parameter is a fundamental parameter for graph theory.
6e`meCoursCoursMPRI20102011 Treewith
Some examples
1.Gis a tree ifftreewidth(G) = 1 2.treewidth(Kn) =n1 3.IfGis a cycle thentreewidth(G) = 2. (It can be seen as two chains in parallel, i.e. a series-parallel graph) 4.treewidth(Kn,m) =min(n,m) 5.treewidth(Gn,m) =min(n,m), the lower bound is hard to obtain ! 6.treewidth(G) (resp. pathwidth) measures the distance fromG to a tree (resp. to a chain)
Easy properties
treewidth(G) =kiffGcan be decomposed using only separators of size less than k. Fundamental lemma Letaban edge ofTsome tree decomposition ofGandT1,T2be the two connected components ofTab, thenVaVbis a separator betweenV1V2andV2V1, whereV1=iT1Viand V2=jT2Vj.
6e`meCoursCoursMPRI20102011 Treewith
Proof of the lemma
De´monstration. Letabbe an edge of a tree decompositionTofG.Tabis disconnected intoT1andT2, two subtrees ofT. LetV1=tT1VtandV2=tT2Vt. IfVaVbis not a separator, then it existsuV1V2andvV2V1anduvE. But then in which bag can the edgeuvbelongs to ? Since using property (i) of tree decomposition each edge must belong to some bag. This cannot be inT1, neither inT2, a contradiction.
6e`meCoursCoursMPRI20102011 Treewith
For the previous lemma, we only use the definition of any tree-decomposition, not an optimal one. It also explains the use of property (i) in the definition of tree decomposition.
6e`meCoursCoursMPRI20102011 Treewith
Computations of treewidth
There exists polynomial approximation algorithms For every fixedk, it exists a linear algorithm to check wether Treewidth(G)kBoedlander 1992. (Big constant for the linearity). Find an efficient algorithm for small values 3,4,5. . .is still a research problem