¿Qué tan grande es el ancho de un árbol que puede tener un árbol más la mitad de los bordes?

14

Deje que G sea un árbol en 2n vértices. El ancho de árbol de G, tw (G) = 1. Ahora supongamos que agregamos n aristas a G para obtener un gráfico H. Un límite superior fácil en tw (H) es n + 1. ¿Es esto esencialmente el mejor posible?

Parece de alguna manera que tw (H) debería ser O (sqrt (n)), pero esto es solo un presentimiento vago. ¿Conocemos mejores límites superiores que O (n) para el ancho de árbol de un gráfico obtenido al agregar n aristas a un árbol en vértices 2n?

upper-bounds treewidth gphilip
fuente

Respuestas:

18

Su modelo no es realmente menos general que preguntar sobre gráficos arbitrarios de 3 regulares, y los gráficos expansores de 3 regulares tienen un ancho de árbol lineal. Entonces no sé acerca de los factores constantes, pero Θ (n) es lo mejor posible, sí.

David Eppstein
fuente
3
Gracias, eso responde mi pregunta. Para elaborar un poco la respuesta de David, deje que H sea un gráfico 3-regular conectado en 2n vértices. H entonces tiene 3n aristas. Sea G un árbol en 2n vértices obtenidos al eliminar n + 1 bordes de H. Agregar n de estos bordes nuevamente a G nos dará H '= (H menos un borde). Al dejar que H sea un gráfico expansor con treewidth \ theta (n), vemos que H 'también tiene treewidth \ theta (n).
gphilip
8

Como señaló David, básicamente pide límites en el ancho del árbol de un gráfico conectado con un grado medio 3. Para el caso más especial de gráficos de 3 regulares, se pueden obtener los siguientes límites inferior y superior. Denotando por pw (G) el ancho de ruta de un gráfico G, está claro que

(1) tw (G) <= pw (G) para cualquier gráfico G (como una descomposición de ruta es una descomposición de árbol)

Está demostrado en [1] que

(2) Para cada \ epsilon> 0, existe un número entero n_0 tal que para cualquier gráfico 3 G regular en n> = n_0 vértices, pw (G) <= n / 6 + \ epsilon * n.

Esto le da un límite superior de aproximadamente n / 6 en el ancho de árbol de los gráficos de 3 regulares.

Para un límite inferior casi seguro, cito de [2]:

"Como los gráficos cúbicos aleatorios casi seguramente tienen un ancho de bisección de al menos 0.101 n (Kostochka, Melnikov, 1992), casi seguramente no tienen separador de tamaño menor que n / 20" y, por lo tanto, casi seguramente no hay descomposición de árboles de ancho menor que n / 20 .

Para un límite inferior "seguro" en el ancho de bisección, [3] mostró una familia infinita de gráficos 3-regulares, de modo que cada gráfico G = (V, E) en esta familia tiene un ancho de bisección de al menos 0.082 * | V |.

[1] Fedor V. Fomin, Kjartan Høie: ancho de ruta de gráficos cúbicos y algoritmos exactos. Inf. Proceso. Letón. 97 (5): 191-196 (2006)

[2] Jaroslav Nesetril, Patrice Ossona de Mendez: Grad y clases con expansión 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: Nuevos límites inferiores espectrales en el ancho de bisección de los gráficos. Theor Comput Sci. 320 (2-3): 155-174 (2004)

Serge Gaspers
fuente
Gracias Serge. El límite a través del ancho de ruta es probablemente más accesible para mí en esta etapa que el que está a través de los gráficos de expansión; Sin embargo, todavía no he leído ninguna prueba.
gphilip