algorithm - simple - Subgrafo conectado mínimo que contiene un conjunto dado de nodos

subgrafo inducido (4)

Tengo un gráfico no ponderado, conectado. Quiero encontrar un subgrafo conectado que incluya definitivamente un determinado conjunto de nodos y la menor cantidad de extras posibles. ¿Cómo podría lograrse esto?

Por si acaso, replantearé la pregunta usando un lenguaje más preciso. Sea G (V, E) una gráfica no ponderada, no dirigida y conectada. Sea N un subconjunto de V. ¿Cuál es la mejor manera de encontrar el subgrafo conectado más pequeño G ''(V'', E '') de G (V, E) de modo que N sea un subconjunto de V''?

Las aproximaciones están bien.

Este es exactamente el conocido problema NP-hard Steiner Tree . Sin más detalles sobre cómo se ven sus instancias, es difícil dar consejos sobre un algoritmo apropiado.

Las soluciones más fáciles serán las siguientes:

a) basado en mst: - inicialmente, todos los nodos de V están en V ''- construye un árbol de expansión mínimo del gráfico G (V, E) - llámalo T.
- bucle: para cada hoja v en T que no esté en N, borre v de V ''.
- Repetir bucle hasta que todas las hojas en T estén en N.

b) otra solución es la siguiente, basada en el árbol de rutas más cortas.
- elija cualquier nodo en N, llámelo v, sea v una raíz de un árbol T = {v}. - eliminar v de N.

bucle: 1) seleccione la ruta más corta desde cualquier nodo en T y cualquier nodo en N. la ruta más corta p: {v, ..., u} donde v está en T yu está en N. 2) cada nodo en p se añade a V ''. 3) todos los nodos en p y en N se eliminan de N. --- repita el ciclo hasta que N esté vacío.

Al comienzo del algoritmo: calcule todas las rutas más cortas en G usando cualquier algoritmo eficiente conocido.

Personalmente, utilicé este algoritmo en uno de mis artículos, pero es más adecuado para entornos distribuidos. Sea N el conjunto de nodos que necesitamos para interconectar. Queremos construir un conjunto dominador conectado mínimo del gráfico G, y queremos dar prioridad a los nodos en N. Le damos a cada nodo un identificador único id (u). Dejamos que w (u) = 0 si u está en N, de lo contrario w (1). Creamos un par (w (u), id (u)) para cada nodo u.

cada nodo u construye un nodo repetidor multiset. Es decir, un conjunto M (u) de neigbhors de 1 salto tal que cada vecino de 2 saltos es un vecino de al menos un nodo en M (u). [El mínimo M (u), mejor es la solución].
u está en V ''si y solo si: u tiene el par más pequeño (w (u), id (u)) entre todos sus vecinos. o u se selecciona en M (v), donde v es un vecino de 1 salto de u con el más pequeño (w (u), id (u)).

- el truco cuando ejecutas este algoritmo de manera centralizada es ser eficiente en el cálculo de vecinos de 2 saltos. Lo mejor que pude obtener de O (n ^ 3) es a O (n ^ 2.37) mediante la multiplicación de matrices.

- Realmente deseo saber cuál es la proporción aproximada de esta última solución.

Me gusta esta referencia para las heurísticas del árbol steiner: El problema del árbol Steiner, Hwang Frank; Richards Dana 1955- Winter Pawel 1952

No puedo pensar en un algoritmo eficiente para encontrar la solución óptima, pero asumiendo que su gráfico de entrada es denso, lo siguiente podría funcionar lo suficientemente bien:

Convierta su gráfico de entrada G(V, E) en un gráfico ponderado G''(N, D) , donde N es el subconjunto de vértices que desea cubrir y D es distancias (longitudes de trayectoria) entre los vértices correspondientes en el gráfico original. Esto "colapsará" todos los vértices que no necesitas en los bordes.
Calcule el árbol de expansión mínimo para G'' .
"Expanda" el árbol de expansión mínimo mediante el siguiente procedimiento: para cada borde d en el árbol de expansión mínimo, tome la ruta correspondiente en el gráfico G y agregue todos los vértices (incluidos los puntos finales) en la ruta al conjunto de resultados V'' y todos los bordes en la ruta al conjunto de resultados E'' .

Este algoritmo es fácil de disparar para dar soluciones subóptimas. Caso de ejemplo: triángulo equilátero donde hay vértices en las esquinas, en los puntos medios de los lados y en el centro del triángulo, y bordes a lo largo de los lados y desde las esquinas hasta la mitad del triángulo. Para cubrir las esquinas, basta con seleccionar el punto central del triángulo, pero este algoritmo puede elegir los lados. No obstante, si el gráfico es denso, debería funcionar bien.

Podrías intentar hacer lo siguiente:

Creando una cubierta de vértice mínima para los nodos deseados N
Contraiga estos sub-gráficos, posiblemente desconectados, en nodos "grandes". Es decir, para cada subgráfico, elimínelo del gráfico y sustitúyalo por un nuevo nodo. Llame a este conjunto de nodos N'' .
Haga una mínima cobertura de vértice de los nodos en N'' .
"Desempaquetar" los nodos en N'' .

No estoy seguro de si te da o no una aproximación dentro de algún límite específico o algo así. Quizás incluso puedas engañar al algoritmo para tomar algunas decisiones realmente estúpidas.