Enumeración de gráficos planos de ancho de árbol acotado

9

Estoy buscando referencias para el siguiente problema: dados los enteros y , enumere todos los gráficos planos no isomórficos en vértices y ancho de árbol \ leq k . Me interesan los resultados teóricos y prácticos, pero en su mayoría algoritmos prácticos que son posibles de codificar y ejecutar para valores tan grandes como sea posible de n y k (piense en k \ leq 5 y n \ leq 15 ). Si ya tiene una respuesta, ignore las divagaciones a continuación.norteknorteknortekk5 5norte15

El siguiente enfoque funciona bastante bien para enumerar todos los gráficos no isomórficos en norte vértices y ancho de árbol k (es decir, cuando se elimina la restricción de planaridad):

(a) Enumere todos los gráficos no isomorfos en vértices norte-1 y ancho de árbol k .

(b) Para cada vértice sol en norte-1 vértices y ancho de árbol k , cada camarilla C en k vértices en sol y cada subconjunto S de bordes en C , haga sol de sol-S agregando un nuevo vértice v adyacente a C . Agregue sol a la lista L de grahs en norte vértices y ancho de árbol k .

(c) Recorte L eliminando copias del mismo gráfico.

Una forma tentadora de extender esto para enumerar gráficos planos de ancho de árbol k es simplemente filtrar los gráficos no planos en cada iteración. Desafortunadamente, esto no puede generar todos los gráficos planos de ancho de árbol k (por ejemplo, porque solo enumera gráficos de 4 4 degenerados).

Por supuesto, podríamos enumerar todos los gráficos en norte vértices y ancho de árbol k y solo luego filtrar los no planos, pero esto no explota que la mayoría de los gráficos no son planos y parece muy subóptimo.

daniello
fuente
¿Estás seguro de que quieres implementarlo y probar el resultado? El número de árboles no isomórficos ya es exponencial.
Saeed
@Saeed: claro: para 20 nodos, el número de árboles es inferior a un millón, por lo que espero que esto sea factible al menos para . norte15
daniello
1
¿qué tal comenzar desde -vertex gráficos cordales de tamaño máximo de camarilla , y eliminar bordes para hacerlo plano? nk+1
Yixin Cao
@Yixin Cao, esto se parece a enumerar gráficos + descomposiciones de árboles de ellos (es decir, el mismo gráfico se ve una vez por árbol de descomposición). Hasta ahora eso ha sido bastante lento (pero alguna optimización podría hacer que este enfoque sea viable)
daniello
2
@daniello, veo su punto pero vio esta aplicación: cs.anu.edu.au/~bdm/plantri , afirman que pueden generar gráficos planos 1M en un segundo (con respecto al isomorfismo). (sin embargo, no es exactamente lo que desea, para 1-2-3 gráficos planos conectados parece ser perfecto, sin embargo, no hay muchos 4-5 gráficos planos conectados en 15 vértices).
Saeed

Respuestas:

2

Hay un buen software que genera pequeños gráficos planos con respecto al isomorfismo que podrían ayudar. Como veo, uno de los problemas era generar gráficos planos no isomórficos y la mayoría de esos gráficos planos (en menos de 15 vértices) son de pequeño ancho de árbol.

Para verificar si su ancho de árbol es más pequeño que el valor dado , una forma es usar algoritmos heurísticos para acelerar este cálculo, solo en el caso de que los algoritmos exactos no sean prácticos. Por ejemplo, en un gráfico plano primero podemos encontrar un diámetro de y la ruta correspondiente de longitud (que es un diámetro). Entonces encontrar un vértice que tiene más corta distancia más larga ( ) a cualquier otro vértice entre todos los vértices . El ancho de árbol de es como máximo , si es menor queG G P d v P l u G P w P G d + l kkGGPdvPluGPwPGd+lk entonces hemos terminado de lo contrario, ya sea aplicar algunos otros algoritmos heurísticos o ejecutar el algoritmo exacto.

Para gráficos de menos de 3 conectados también es posible aplicar heurística encontrando vértices cortados y luego arreglando esos vértices y encontrando el ancho del árbol de un gráfico restante. Pero como el número de nodos es pequeño ( ) si el gráfico está conectado a entonces el diámetro no es grande y creo que la primera heurística debería funcionar allí. (No sé si hay algún 5 grafo plano conectado a un máximo de 15 vértices, pero como sabemos no hay comunicado con los planos gráfico para )4 t t > 5154tt>5 5

Como no se conoce el tamaño de la mayor obstrucción para el ancho del árbol no podemos simplemente adivinar el valor superior del ancho del árbol de un gráfico dado . Pero parece que al menos para las gráficas planas no debería ser tan grande (uno debería dar una prueba de esto).Gksol

Saeed
fuente
1

Se pueden enumerar todos los pares donde G es un gráfico plano con un ancho de árbol como máximo k , B es una bolsa de tamaño k, de modo que existe una descomposición de árbol de G con B como bolsa.sol,sisolksiksolsi

Ahora, para cada par donde G tiene n - 1 vértices, construimos un nuevo gráfico G ' para cada subconjunto S de B agregando un vértice v con S como vecinos y dejando que B ' sea ​​un subconjunto de tamaño k de B v . Agregue G , B si G es plano y no isomorfo a cualquier par ya encontrado.sol,sisolnorte-1solSsivSsiksivsol,sisol

Un límite superior fácil sobre cuántas entradas hay que almacenar es veces el número de gráficos enumerados, pero este es un límite pesimista. Para la mayoría de los gráficos de ancho de árbol k, la mayoría de los subconjuntos de tamaño k no pueden batear, por ejemplo, una cuadrícula solo tiene bolsas posibles. k×nn3k-1(nortek)k×nortenorte3k-1

Creo que esto funcionará tan bien como el algoritmo para gráficos no planos, ya que para cada par G, B obtenemos un gráfico al hacer de B una camarilla, la mayoría de estos gráficos no serán isomórficos.

Hay varios trucos que uno puede aplicar para acelerar esto, sugeriría buscar en: http://www.siam.org/meetings/alenex04/abstacts/HBodlaender.pdf

Martin Vatshelle
fuente
¿No todos los gráficos enumerados tienen ancho de ruta acotado en lugar de ancho de árbol?
daniello
Creo que tienes razón. La elección de B 'es demasiado limitada.
Martin Vatshelle