7ème Cours Cours MPRI 2010–2011

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

Description

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

Informations

• Publié par: Thoim
• Nombre de lectures: 14
• Langue: English

Extrait

7`emeCours

Cours MPRI 2010–2011

7e`meCours Cours MPRI 2010–2011

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

Chevaleret, november 2010

7`emeCoursCoursMPRI2010–2011

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`emeCoursCoursMPRI2010–2011 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, 80≤treewidth(N)≤160

7e`meCoursCoursMPRI2010–2011 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 gridG r,r as minor and we find a vertexx s.t. : Ghas a solution iffG−xhas a solution. 3.Recurse onG−x

7e`meCoursCoursMPRI2010–2011 Some remarks on treewidth

Bramble again

I

I

For a connected graphG, the set of all connected subgraphs withd n 2 evertices is a bramble ofG. Another proof ofbn(G)<treewidth(G) using Helly s ’ property.

7e`meCoursCoursMPRI2010–2011 Some remarks on treewidth

About Courcelle’s meta theorem

I Many problems can be expressed in MSO I But not all, for example Isomorphism cannot be expressed in MSO I But isomorphism is polynomial for bounded treewidth graphs. Monadic Second Order logic (quantifiers on set variables : unary objects) I Bounded treewidth graphs are sparse since : |E| ≤k|V|

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

Some remarks on treewidth

Exercices :

I

I

IfH≤G

(minor ordering), have we :cw(H)≤cw(G) ?

Gs.t.treewidth(G)≤kcan be formulated using MSO ?

Definition To each partition{A,V−A}deVone can associate a weight ω(A). ω: 2 V →Zis a connectivity function if : (i)ω(A) =ω(V-A) (ii)Submodularityω(A) +ω(B)≥ω(A∪B) +ω(A∩B) (iii)ω(∅) = 0

LetVbe a finite set, a pair (T, δ) is a branch decomposition of V, ifTis a ternary tree (∀t∈T,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`eoursursC0201PMIR B 1 ar 2–10 unctionshdncomecsipoonticdnaennovitcfyti

7e`meCoursCoursMPRI2010–2011

Branch decomposition and connectivity functions

Definition ofω-width

I

I

For every weight functionω: ω(T, δ) =max A cut of T {ω({A,V-A})}. branch-dec(V) =min (T,δ) {ω(T, δ)}.