Qual a largura de uma árvore, mais a metade das bordas?

14

Seja G uma árvore em 2n vértices. A largura de árvore de G, tw (G) = 1. Agora, suponha que adicionemos n arestas a G para obter um gráfico H. Um limite superior fácil de tw (H) é n + 1. Isso é essencialmente o melhor possível?

Parece de alguma forma que tw (H) deve ser O (sqrt (n)), mas isso é apenas um palpite vago. Conhecemos limites superiores melhores que O (n) para a largura de árvore de um gráfico obtido pela adição de n arestas a uma árvore em 2n vértices?

upper-bounds treewidth gphilip
fonte

Respostas:

18

Seu modelo não é menos genérico do que perguntar sobre gráficos 3-regulares arbitrários, e os gráficos do expansor 3-regulares têm largura de árvore linear. Portanto, não sei sobre fatores constantes, mas Θ (n) é melhor possível, sim.

David Eppstein
fonte
3
Obrigado, isso responde à minha pergunta. Para elaborar um pouco a resposta de David, seja H um gráfico 3-regular conectado em 2n vértices. H tem então 3n arestas. Seja G uma árvore em 2n vértices obtidos pela remoção de n + 1 arestas de H. A adição de n dessas arestas de volta a G nos dará H '= (H menos uma aresta). Permitindo que H seja um gráfico de expansão com largura da árvore \ theta (n), vemos que H 'também tem largura da árvore \ theta (n).
Gphilip 17/08/10
8

Como David apontou, você basicamente pede limites na largura da árvore de um gráfico conectado com grau médio 3. No caso mais especial de gráficos tridimensionais, os seguintes limites inferior e superior podem ser obtidos. Denotando por pw (G) a largura do caminho de um gráfico G, fica claro que

(1) tw (G) <= pw (G) para qualquer gráfico G (como uma decomposição de caminho é uma decomposição em árvore)

Está provado em [1] que

(2) Para todo \ epsilon> 0, existe um número inteiro n_0 tal que para qualquer gráfico tridimensional G em n> = n_0 vértices, pw (G) <= n / 6 + \ epsilon * n.

Isso fornece um limite superior de aproximadamente n / 6 na largura da árvore dos gráficos tridimensionais.

Para um limite inferior quase certo, cito de [2]:

"Como os gráficos cúbicos aleatórios quase certamente têm largura de bissecção de pelo menos 0,101 n (Kostochka, Melnikov, 1992), eles quase certamente não têm separador de tamanho menor que n / 20" e, portanto, quase certamente não há decomposição de árvore com largura menor que n / 20 .

Para um limite inferior "seguro" na largura da bissecção, [3] mostrou uma família infinita de gráficos tridimensionais, de modo que cada gráfico G = (V, E) nessa família tenha uma largura de bissecção de pelo menos 0,082 * | V |.

[1] Fedor V. Fomin, Kjartan Høie: largura de caminho de gráficos cúbicos e algoritmos exatos. Inf. Processo. Lett. 97 (5): 191-196 (2006)

[2] Jaroslav Nesetril, Patrice Ossona de Mendez: graduado e classes com expansão limitada II. Aspectos algorítmicos. EUR. J. Comb. 29 (3): 777-791 (2008)

[3] Sergei L. Bezrukov, Robert Elsässer, Burkhard Monien, Robert Preis, Jean-Pierre Tillich: Novos limites espectrais inferiores na largura da bissecção dos gráficos. Theor. Comput. Sci. 320 (2-3): 155-174 (2004)

Serge Gaspers
fonte
Obrigado Serge. O limite via largura de caminho provavelmente é mais acessível para mim nesse estágio do que aquele via gráficos de expansão; Ainda não li nenhuma das provas.
Gphilip