Bedeutet Baumbreite

12

Sei k fest und sei G ein (zusammenhängender) Graph. Wenn ich mich nicht irre, folgt aus der Arbeit von Bodlaender [1, Theorem 3.11], dass, wenn die Baumbreite von G ungefähr mindestens beträgt 2k3, G einen Stern K1,k als Moll enthält.

Können wir den Term kleiner machen? Das heißt, impliziert eine Baumbreite von mindestens k bereits die Existenz eines K 1 , k -minderjährigen? Gibt es irgendwo einen Beweis?2k3kK1,k


[1] Bodlaender, HL (1993). Bei linearer Zeit werden kleinere Tests mit Tiefensuche durchgeführt. Journal of Algorithms, 14 (1), 1-23.

Juho
quelle
2
Ein lose verwandtes Ergebnis von Demaine und Hajiaghayi : Für einen festen Graphen hat jeder H- minderwertige Graph der Baumbreite w ein Ω ( w ) × Ω ( w ) Gittergraphenmoll. HHwΩ(w)×Ω(w)
mhum
1
@mhum die Konstante in hängt exponentiell von | ab H | Wenn Sie dies also direkt anwenden, erhalten Sie eine Grenze von weniger als 2 k 3 . Ω|H|2k3
Daniello
@daniello Das ist ja der Fall. Die Konstante ist nicht sehr schön und die Spezialisierung auf Minor-freie Graphen ist auch nicht so toll. Ich wollte nur auf ein vage verwandtes Ergebnis hinweisen. H
mhum

Antworten:

15

Es ist in der Tat wahr, dass jeder Graph ohne K 1 , k - Moll höchstens eine Baumbreite von k - 1 hat . Wir beweisen hierzu nachfolgend zunächst einige Definitionen:GK1,kk1

Lassen sein , die von Baumweite G und ω ( G ) sein , die maximale Größe einer Clique in G . Ein Graph H ist eine Triangulation von G, wenn G ein Teilgraph von H ist und H akkordisch ist (dh keine induzierten Zyklen auf mindestens 4 Eckpunkten hat). Eine Triangulation H von G ist eine minimale Triangulation, wenn kein geeigneter Teilgraph von H auch eine Triangulation von G ist . Eine Teilmenge X von Eckpunkten von Gtw(G)Gω(G)GHGGHH4HGHGXGist eine potentielle maximale Clique, wenn es eine minimale Triangulation von G gibt, so dass X eine maximale Clique von H ist . Es ist bekannt, dass t w ( G ) = min H ω ( H ) - 1 ist. Hier wird das Minimum über alle minimalen Triangulationen H von G genommen .HGXH

tw(G)=minHω(H)1
HG

Die obige Formel impliziert, dass es ausreicht , um zu beweisen, dass ist, dass alle potenziellen maximalen Cliquen von G eine Größe von höchstens k haben . Das beweisen wir jetzt. Sei X eine potentielle maximale Clique von G und nehme an, dass | X | k + 1 .tw(G)k1GkXG|X|k+1

Wir werden die folgende Charakterisierung von potentieller maximaler Clique verwenden: a Artikulationssatz ist eine potentielle maximale Clique in G , wenn, und nur wenn, für jedes Paar u , v nicht benachbarter (distinct) Eckpunkte in X ein Pfad ist , P u , v von u zu v in G mit all ihren inneren Ecken außerhalb von X . Diese Charakterisierung findet sich in der Arbeit Treewidth and Minimum Fill-in: Gruppierung der Mindesttrennzeichen nach Bouchitte und Todinca.XGuvXPu,vuvGX

Mit dieser Charakterisierung ist es einfach, aus X ein Moll abzuleiten . Lassen Sie u X . Für jeden Scheitelpunkt v X { u } , entweder u v eine Kante von G , oder es ist ein Pfad P u , v von u zu v mit allen internen Scheiteln außerhalb X . Für alle v X , die nicht an u angrenzen, ziehen Sie alle inneren Eckpunkte von P u zusammenK1,kXuXvX{u}uvGPu,vuvXvXu inu. Am Ende haben wir ein Moll vonG,in demuanXangrenzt, und | X | k+1. Der Grad vonuin diesem Moll ist also mindestensk, was den Beweis vervollständigt.Pu,vuGuX|X|k+1uk

daniello
quelle
Danke Daniel! Wissen Sie zufällig, ob dasselbe Argument (oder dasselbe Ergebnis wirklich) irgendwo veröffentlicht wurde?
Juho
Ich habe keine Referenz, aber ich scheine mich zu erinnern, dass ein ähnlich aussehendes (möglicherweise weniger strenges) Argument für freie Graphen irgendwo geschrieben wurde. Leider habe ich keinen konkreten Hinweis. K2,r
Daniello