Quelle largeur d'arbre peut avoir un arbre plus la moitié des bords?

14

Soit G un arbre sur 2n sommets. La largeur d'arbre de G, tw (G) = 1. Supposons maintenant que nous ajoutons n arêtes à G pour obtenir un graphique H. Une borne supérieure facile sur tw (H) est n + 1. Est-ce essentiellement la meilleure possible?

Il semble que tw (H) devrait être O (sqrt (n)), mais ce n'est qu'un vague pressentiment. Connaissons-nous de meilleures limites supérieures que O (n) pour la largeur d'arbre d'un graphe obtenue en ajoutant n arêtes à un arbre sur 2n sommets?

upper-bounds treewidth gphilip
la source

Réponses:

18

Votre modèle n'est pas vraiment moins général que de poser des questions sur des graphes arbitraires à 3 réguliers, et les graphes à 3 expanseurs réguliers ont une largeur d'arbre linéaire. Je ne connais donc pas les facteurs constants, mais Θ (n) est le mieux possible, oui.

David Eppstein
la source
3
Merci, cela répond à ma question. Pour élaborer un peu la réponse de David, supposons que H soit un graphe 3-régulier connecté sur 2n sommets. H a alors 3n arêtes. Soit G un arbre sur 2n sommets obtenu en supprimant n + 1 arêtes de H. Ajouter n de ces arêtes à G nous donnera H '= (H moins une arête). Soit H un graphe expanseur avec une largeur d'arbre \ theta (n), nous voyons que H 'a aussi une largeur d'arbre \ theta (n).
gphilip
8

Comme l'a souligné David, vous demandez essentiellement des limites sur la largeur d'arbre d'un graphique connecté avec un degré moyen 3. Pour le cas plus spécial des graphiques à 3 régularités, les limites inférieures et supérieures suivantes peuvent être obtenues. Notant par pw (G) la largeur de chemin d'un graphe G, il est clair que

(1) tw (G) <= pw (G) pour tout graphique G (car une décomposition de chemin est une décomposition d'arbre)

Il est prouvé dans [1] que

(2) Pour chaque \ epsilon> 0, il existe un entier n_0 tel que pour tout graphe 3 régulier G sur n> = n_0 sommets, pw (G) <= n / 6 + \ epsilon * n.

Cela vous donne une limite supérieure d'environ n / 6 sur la largeur de l'arborescence des graphiques 3-réguliers.

Pour une borne inférieure presque sûre, je cite de [2]:

"Comme les graphiques cubiques aléatoires ont presque sûrement une largeur de bissection d'au moins 0,101 n (Kostochka, Melnikov, 1992), ils n'ont presque sûrement pas de séparateur de taille inférieure à n / 20" et donc presque sûrement pas de décomposition d'arbre de largeur inférieure à n / 20 .

Pour une borne inférieure "sûre" sur la largeur de bissection, [3] a montré une famille infinie de graphes à 3 régularités, de sorte que chaque graphique G = (V, E) de cette famille a une largeur de bissection d'au moins 0,082 * | V |.

[1] Fedor V. Fomin, Kjartan Høie: largeur de chemin des graphes cubiques et algorithmes exacts. Inf. Processus. Lett. 97 (5): 191-196 (2006)

[2] Jaroslav Nesetril, Patrice Ossona de Mendez: Diplômé et classes avec expansion bornée II. Aspects algorithmiques. EUR. J. Comb. 29 (3): 777-791 (2008)

[3] Sergei L. Bezrukov, Robert Elsässer, Burkhard Monien, Robert Preis, Jean-Pierre Tillich: Nouvelles limites spectrales inférieures sur la largeur de bissection des graphiques. Théor. Comput. Sci. 320 (2-3): 155-174 (2004)

Serge Gaspers
la source
Merci, Serge. La borne via pathwidth est probablement plus accessible pour moi à ce stade que celle via les graphes expanseurs; Cependant, je n'ai pas encore lu les preuves.
gphilip