# 7ème Cours Cours MPRI 2010–2011

-

English
37 Pages
Learn all about the services we offer

Description

7eme Cours Cours MPRI 2010{20117eme CoursCours MPRI 2010{2011Michel Habibhabib@liafa.jussieu.frhttp://www.liafa.jussieu.fr/ habib~Chevaleret, november 20107eme Cours Cours MPRI 2010{2011ScheduleSome remarks on treewidthBranch decomposition and connectivity functionsCoping with branchwidthRelationships between treewidth and branchwidthRankwidthSome relationships between these widthsThe boolean matrix multiplication complexity barrier7eme Cours Cours MPRI 2010{2011Some remarks on treewidthSome applications of treewidthI Packman from V. Limouzy (f^ete de la science 2007)Playing with Packman is equivalent to compute the treewidthof a special graph (3 or 4)I Treewidth de l’internet ...... Laurent ViennotFor a network of routers N, 80 treewidth(N) 1607eme Cours Cours MPRI 2010{2011Some remarks on treewidthExamples of non constructive algorithms1. For any xed k, it is polynomial to test wheter genius(G ) k(we know there is a nite number of obstructions)2. It is polynomial to decide if a graph has a non-crossingembedding in 3D(non-crossing means no 2 cycles cross)7eme Cours Cours MPRI 2010{2011Some remarks on treewidthB. Reed’s algorithm for disjoint path problem1. If treewidth(G ) k then using Courcelle’s meta theorem, itcan be solved in linear time.2. Else G contains a grid G as minor and we nd a vertex xr;rs.t. :G has a solution i G x has a solution.3. Recurse on G x7eme Cours Cours MPRI 2010{2011Some remarks on ...

Subjects

##### Formal sciences

Informations

Report a problem
7`emeCours
Cours MPRI 2010–2011
7e`meCours Cours MPRI 2010–2011
Michel Habib habib@liafa.jussieu.fr http://www.liafa.jussieu.fr/~habib
Chevaleret, november 2010
7`emeCoursCoursMPRI20102011
Schedule
Some remarks on treewidth
Branch decomposition and connectivity functions
Coping with branchwidth
Relationships between treewidth and branchwidth
Rankwidth
Some relationships between these widths
The boolean matrix multiplication complexity barrier
7`emeCoursCoursMPRI20102011 Some remarks on treewidth
Some applications of treewidth
I
I
PackmanfromV.Limouzy(feˆtedelascience2007) Playing with Packman is equivalent to compute the treewidth of a special graph (3 or 4) Treewidth de l’internet ...... Laurent Viennot For a network of routersN, 80treewidth(N)160
7e`meCoursCoursMPRI20102011 Some remarks on treewidth
Examples of non constructive algorithms
1. 2.
For any ﬁxedk, it is polynomial to test whetergenius(G)k (we know there is a ﬁnite number of obstructions) It is polynomial to decide if a graph has a non-crossing embedding in 3D (non-crossing means no 2 cycles cross)
7` e Cours Cours MPRI 2010–2011 em Some remarks on treewidth
B. Reed’s algorithm for disjoint path problem
1.Iftreewidth(G)kthen using Courcelle’s meta theorem, it can be solved in linear time. 2.ElseGcontains a gridGr,ras minor and we ﬁnd a vertexx s.t. : Ghas a solution iﬀGxhas a solution. 3.Recurse onGx
7e`meCoursCoursMPRI20102011 Some remarks on treewidth
Bramble again
I
I
For a connected graphG, the set of all connected subgraphs withdn2evertices is a bramble ofG. Another proof ofbn(G)<treewidth(G) using Helly s property.
7e`meCoursCoursMPRI20102011 Some remarks on treewidth
IMany problems can be expressed in MSO IBut not all, for example Isomorphism cannot be expressed in MSO IBut isomorphism is polynomial for bounded treewidth graphs. Monadic Second Order logic (quantiﬁers on set variables : unary objects) IBounded treewidth graphs are sparse since : |E| ≤k|V|
7e`meCoursCoursMPRI20102011 Some remarks on treewidth
I I I
But all interesting graphs are sparse ! Real graphs coming from applications are often sparse (as for example networks for which every edge has a cost). The search of linear time algorithms inO(n+m) is interesting only for sparse graphs.
7`emeCoursCoursMPRI20102011
Some remarks on treewidth
Exercices :
I
I
IfHG
(minor ordering), have we :cw(H)cw(G) ?
Gs.t.treewidth(G)kcan be formulated using MSO ?
Deﬁnition To each partition{A,VA}deVone can associate a weight ω(A). ω: 2VZis a connectivity function if : (i)ω(A) =ω(V-A) (ii)Submodularityω(A) +ω(B)ω(AB) +ω(AB) (iii)ω() = 0
LetVbe a ﬁnite set, a pair (T, δ) is a branch decomposition of V, ifTis a ternary tree (tT,degree(t)3), andδis a bijection mapping the elements ofVto the leaves ofT. To each edge ofT, corresponds a bipartition ofVor a cut.
meCo7`eoursursC0201PMIRB1ar210unctionshdncomecsipoonticdnaennovitcfyti
7e`meCoursCoursMPRI20102011
Branch decomposition and connectivity functions
Deﬁnition ofω-width
I
I
For every weight functionω: ω(T, δ) =maxA cut of T{ω({A,V-A})}. branch-dec(V) =min(T){ω(T, δ)}.
en expand_more