6ème Cours Cours MPRI 2010–2011

Michel Habib [e-mail] ` `%%%`#`&12_`__~~~ Alse

Description

6eme Cours Cours MPRI 2010{20116eme CoursCours MPRI 2010{2011Michel [e-mail]://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 ...

Informations

• Publié par: Syas
• Nombre de lectures: 30
• Langue: English

Extrait

6`emeCours

Cours MPRI 2010–2011

6e`meCours Cours MPRI 2010–2011

Michel Habib [e-mail] http://www.liafa.jussieu.fr/ ~ habib

Chevaleret, october 2010

6`emeCoursCoursMPRI2010–2011

Schedule

Treewith

Graph Minors

Big theorems on Graph Minors

Other width parameters

Cliquewidth

e`6em rT C ee uo iw r t s h oCrusPMRI2010–2011

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)∀e∈E,∃i∈Iwithe∈G(S i ). (ii)∀x∈V, the elements of S containingxform a subtree ofT.

Definition treewidth(G) =Min D (Max S i ∈S {|S i | −1})

6`eme

Cours

Treewith

Cours

MPRI

2010–2011

6e`meCoursCoursMPRI2010–2011

Treewith

Recall

1. 2.

of some Equivalences

Treewidth(G) =Min H triangulation of Computing treewidth is NP-hard.

G {ω(H)−1}

6`emeCoursCoursMPRI2010–2011 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`meCoursCoursMPRI2010–2011 Treewith

Some examples

1.Gis a tree ifftreewidth(G) = 1 2.treewidth(K n ) =n−1 3.IfGis a cycle thentreewidth(G) = 2. (It can be seen as two chains in parallel, i.e. a series-parallel graph) 4.treewidth(K n,m ) =min(n,m) 5.treewidth(G n,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`6em Tr C ee uo iw r t s h oCrusPMIR0201–2

Easy properties

101

treewidth(G) =kiffGcan be decomposed using only separators of size less than k. Fundamental lemma Letaban edge ofTsome tree decomposition ofGandT 1 ,T 2 be the two connected components ofT−ab, thenV a ∩V b is a separator betweenV 1 −V 2 andV 2 −V 1 , whereV 1 =∪ i∈T 1 V i and V 2 =∪ j∈T 2 V j .

6e`meCoursCoursMPRI2010–2011 Treewith

Proof of the lemma

De´monstration. Letabbe an edge of a tree decompositionTofG.T−abis disconnected intoT 1 andT 2 , two subtrees ofT. LetV 1 =∪ t∈T 1 V t andV 2 =∪ t∈T 2 V t . IfV a ∩V b is not a separator, then it existsu∈V 1 −V 2 andv∈V 2 −V 1 anduv∈E. 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 inT 1 , neither inT 2 , a contradiction.

6e`meCoursCoursMPRI2010–2011 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`meCoursCoursMPRI2010–2011 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