Wie breit kann ein Baum plus die Hälfte der Ränder sein?

14

Sei G ein Baum auf 2n Eckpunkten. Die Baumbreite von G, tw (G) = 1. Nehmen wir nun an, wir addieren n Kanten zu G, um einen Graphen H zu erhalten. Eine einfache Obergrenze für tw (H) ist n + 1. Ist dies im Wesentlichen die bestmögliche?

Es scheint irgendwie, dass tw (H) O (sqrt (n)) sein sollte, aber dies ist nur eine vage Vermutung. Kennen wir bessere Obergrenzen als O (n) für die Baumbreite eines Graphen, der durch Hinzufügen von n Kanten zu einem Baum auf 2n Eckpunkten erhalten wird?

upper-bounds treewidth gphilip
quelle

Antworten:

18

Ihr Modell ist nicht weniger allgemein als das Nachfragen nach beliebigen 3-regulären Graphen, und 3-reguläre Expander-Graphen haben eine lineare Baumbreite. Ich kenne also keine konstanten Faktoren, aber Θ (n) ist bestmöglich, ja.

David Eppstein
quelle
3
Danke, das beantwortet meine Frage. Um Davids Antwort ein wenig zu erläutern, sei H ein zusammenhängender 3-regulärer Graph auf 2n Eckpunkten. H hat dann 3n Kanten. Sei G ein Baum auf 2n Ecken, der durch Entfernen von n + 1 Kanten von H erhalten wird. Addiert man n dieser Kanten zurück zu G, so erhält man H '= (H minus eine Kante). Wenn H ein Expandergraph mit der Baumbreite tre (n) ist, sehen wir, dass H 'auch die Baumbreite \ (n) hat.
Gphilip
8

Wie David ausführte, fordern Sie im Grunde genommen Schranken für die Baumbreite eines zusammenhängenden Graphen mit Durchschnittsgrad 3 an. Für den spezielleren Fall von 3-regulären Graphen können die folgenden unteren und oberen Schranken erhalten werden. Wenn man die Wegbreite eines Graphen G mit pw (G) bezeichnet, ist das klar

(1) tw (G) <= pw (G) für jeden Graphen G (da eine Pfadzerlegung eine Baumzerlegung ist)

Es ist in [1] bewiesen, dass

(2) Für jedes \ epsilon> 0 existiert eine ganze Zahl n_0, so dass für jeden 3-regulären Graphen G auf n> = n_0 Eckpunkten pw (G) <= n / 6 + \ epsilon * n gilt.

Dies gibt Ihnen eine Obergrenze von ungefähr n / 6 auf der Breite von 3-regulären Graphen.

Für eine fast sichere Untergrenze zitiere ich aus [2]:

"Da zufällige kubische Graphen mit ziemlicher Sicherheit eine Halbierungsbreite von mindestens 0,101 n haben (Kostochka, Melnikov, 1992), haben sie mit ziemlicher Sicherheit kein Trennzeichen mit einer Größe von weniger als n / 20" und somit mit ziemlicher Sicherheit keine Baumzerlegung mit einer Breite von weniger als n / 20 .

Für eine "sichere" Untergrenze der Halbierungsbreite zeigte [3] eine unendliche Familie von 3-regulären Graphen, so dass jeder Graph G = (V, E) in dieser Familie eine Halbierungsbreite von mindestens 0,082 * | V | aufweist.

[1] Fedor V. Fomin, Kjartan Høie: Pfadbreite von kubischen Graphen und exakten Algorithmen. Inf. Prozess. Lette. 97 (5): 191-196 (2006)

Jaroslav Nesetril, Patrice Ossona de Mendez: Grad und Klassen mit begrenzter Expansion II. Algorithmische Aspekte. EUR. J. Comb. 29 (3): 777-791 (2008)

[3] Sergej L. Bezrukow, Robert Elsässer, Burkhard Monien, Robert Preis, Jean-Pierre Tillich: Neue spektrale Untergrenzen für die Halbierungsbreite von Graphen. Theor. Comput. Sci. 320 (2-3): 155-174 (2004)

Serge Gaspers
quelle
Danke, Serge. Die gebundene Via-Pfadbreite ist mir zu diesem Zeitpunkt wahrscheinlich zugänglicher als die Via-Expander-Graphen. Ich habe aber noch keinen Beweis gelesen.
Gphilip