6ème Cours   Cours MPRI 2010–2011
51 Pages
English

6ème Cours Cours MPRI 2010–2011

-

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

Description

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

Subjects

Informations

Published by
Reads 29
Language English
6`emeCours
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
6`emeCoursCoursMPRI20102011
Schedule
Treewith
Graph Minors
Big theorems on Graph Minors
Other width parameters
Cliquewidth
e`6emrTCeeuoiwrtshoCrusPMRI20102011
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})
6`eme
Cours
Treewith
Cours
MPRI
2010–2011
6e`meCoursCoursMPRI20102011
Treewith
Recall
1. 2.
of some Equivalences
Treewidth(G) =MinH triangulation of Computing treewidth is NP-hard.
G{ω(H)1}
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)
e`6emTrCeeuoiwrtshoCrusPMIR02012
Easy properties
101
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
I I
I
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