algorithm - Árbol de expansión que minimiza el número de vértices conectados a varios bordes.

tree graph-theory (3)

¿Existe un algoritmo para encontrar un árbol de expansión de un gráfico no dirigido que minimice el número de vértices conectados a más de un borde?

Por ejemplo, dado un gráfico de cuadrícula de 4 x 4, queremos encontrar un árbol de expansión como el de la izquierda (que tiene 7 vértices conectados a más de un borde) en lugar de el de la derecha (que tiene 12):

Edición: ¿Sería este problema más simple si consideramos solo gráficos planos (o incluso solo gráficos de cuadrícula)?

Como señala Evgeny en los comentarios, esto se conoce como el problema del árbol de expansión de hojas máximo . Me he vinculado al artículo de Wikipedia sobre el problema del conjunto dominante conectado estrechamente relacionado, que es el problema de encontrar un conjunto mínimo de vértices que (i) induzcan un subgrafo conectado (ii) satisfagan la proposición de que, para todos los demás vértices v , algún vértice en el conjunto es adyacente a v. Los dos problemas que se muestran equivalen a una solución al observar que, dado un árbol de expansión, podemos construir un conjunto dominante conectado al eliminar las hojas (vértices con exactamente una conexión), y dado un conjunto dominante conectado, podemos extraer un árbol de expansión del subgrafo inducido y unir los otros vértices como hojas.

Desafortunadamente, ambos problemas son NP-duros, y permanecen NP-hard bajo una restricción a los gráficos planos. No estoy familiarizado con la literatura sobre conjuntos dominantes conectados en particular, pero supongo que hay tres ángulos.

Provablemente "rápido" algoritmos exactos / algoritmos de aproximación exponencial.
Algoritmos exactos que no son demostrablemente rápidos (por ejemplo, programación de enteros) pero buenos en la práctica.
Heurísticas.

El número 1 puede parecer una agrupación extraña, pero lo que suele ocurrir en la literatura de gráficos planares es que los algoritmos exactos se utilizan como una subrutina dentro de los algoritmos de aproximación, a menudo a través de una técnica debida a Brenda Baker, conocida como cambio. Una de las propiedades de los gráficos planos es que un parámetro llamado ancho de árbol está limitado por O (sqrt (n)) en lugar de n, y hay programas dinámicos cuyo exponente de tiempo de ejecución es una función del ancho de árbol mucho más pequeño. (Por ejemplo, en las cuadrículas, puede ejecutar una fila de fila por fila. La maquinaria de descomposición de árbol generaliza esto a gráficos planares arbitrarios).

Es difícil aconsejarle sobre el mejor curso sin saber cómo son las instancias y tal vez incluso sin experimentar con ellas. Probablemente iría por la puerta # 2, pero no estoy seguro de qué aspecto tendría una buena formulación. La buena noticia es que la mayor parte de la complejidad algorítmica se abstrae en la biblioteca de solucionadores que utilizará. Aquí hay una formulación de calidad desconocida.

Para todos los vértices v , sea x_v 1 si v es una hoja y 0 si v es una hoja. La parte dominante del conjunto es fácil.

minimize sum_v x_v subject to for all v, sum_{w such that w = v or w ~ v} x_w >= 1 for all v, x_v in {0, 1}

Aquí estoy usando ~ para significar "está adyacente a". Hacer cumplir la restricción de conectividad es más complicado. El enfoque más simple que se me ocurre es resolver el programa de enteros tal como está, luego buscar dos vértices s y t que estén ambos seleccionados pero no conectados en la solución, calcular un mínimo separador de vértices U entre s y t entre los separadores sin incluir un vértice elegido, ingrese una restricción

(1 - x_s) + (1 - x_t) + sum_{v in U} x_v >= 1

y luego intente de nuevo.

Tendría más esperanza con respecto a un enfoque que utilice muchas variables de manera exponencial, pero puede ser mucho más difícil de implementar (generación de filas y columnas). Elija un vértice r que será forzado como un no-hoja (adivine o pruebe todas las posibilidades). Hay una variable y_P para cada ruta simple P con r como un punto final.

minimize sum_v x_v subject to for all v, for all P having v as an interior vertex, x_v >= y_P for all v, sum_{P having v as an endpoint} y_P >= 1 for all v, x_v in {0, 1} for all P, y_P in {0, 1}

No que yo sepa.

Podría usar un enfoque de búsqueda de amplitud, agregando todos los vértices no visitados a una cola y visitando el siguiente vértice en la cola. Mientras tanto, agregaría vértices y sus bordes a una Cola de prioridad basada en el número de bordes posibles que se ramifican desde el vértice de conexión. Luego recurra a través de la PQ, agregando la mejor ventaja cada vez. Solo tendría que restar valor a los bordes que contienen vértices ya utilizados. Luego, verifique si hubo bordes de mayor prioridad en el último vértice y, si es así, retroceda.

Es un concepto feo y podría ser peor en la implementación.

Para un 4x4 solo necesitaría 7 vértices conectados a más de 1 borde, lo que me daría 9 nodos de hoja.

A medida que las dimensiones aumentan, debe expandirse en el patrón anterior.

Para un 10x10 tendrías 59 nodos de hoja.

Para las cuadrículas donde las filas <> Cols tendrías que probar el patrón en ambas orientaciones para ver cuál produce los mejores resultados.