7ème Cours   Cours MPRI 2010–2011

7ème Cours Cours MPRI 2010–2011

-

Documents
37 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

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

Sujets

Informations

Publié par
Nombre de lectures 14
Langue English
Signaler un problème
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 fixedk, it is polynomial to test whetergenius(G)k (we know there is a finite 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 find a vertexx s.t. : Ghas a solution iffGxhas 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
About Courcelle’s meta theorem
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 (quantifiers 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 ?
Definition 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 finite 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
Definition ofω-width
I
I
For every weight functionω: ω(T, δ) =maxA cut of T{ω({A,V-A})}. branch-dec(V) =min(T){ω(T, δ)}.