k -árbol de expansión mínima

El problema del árbol de expansión mínima k , estudiado en la informática teórica , consiste en encontrar un árbol de coste mínimo con exactamente k vértices que forme un subgrafo de un grafo mayor. También se le conoce como árbol de expansión mínima k o árbol de k cardinalidad ponderado por aristas . Encontrar este árbol es un problema NP-difícil , pero se puede aproximar con una razón de aproximación constante en tiempo polinomial .

La entrada al problema consiste en un grafo no dirigido con pesos en sus aristas y un número k . La salida es un árbol con k vértices y k − 1 aristas, donde todas las aristas del árbol de salida pertenecen al grafo de entrada. El costo de la salida es la suma de los pesos de sus aristas, y el objetivo es encontrar el árbol que tenga el costo mínimo. El problema fue formulado por Lozovanu y Zelikovsky (1993) ^{[ 1 ]} y por Ravi et al. (1996) .

Ravi et al. también consideraron una versión geométrica del problema, que puede verse como un caso especial del problema de grafos. En el problema geométrico del árbol de expansión k -mínimo, la entrada es un conjunto de puntos en el plano. Nuevamente, la salida debe ser un árbol con k de los puntos como vértices, minimizando la longitud euclidiana total de sus aristas. Es decir, es un árbol de expansión k -mínimo de grafos en un grafo completo con distancias euclidianas como pesos. ^{[ 2 ]}

Cuando k es una constante fija, el problema del árbol de expansión k -mínimo se puede resolver en tiempo polinomial mediante un algoritmo de búsqueda por fuerza bruta que prueba todas las k -tuplas de vértices. Sin embargo, para k variable , se ha demostrado que el problema del árbol de expansión k -mínimo es NP-difícil mediante una reducción del problema del árbol de Steiner . ^{[ 1 ] [ 2 ]}

La reducción toma como entrada una instancia del problema del árbol de Steiner: un grafo ponderado, con un subconjunto de sus vértices seleccionados como terminales. El objetivo del problema del árbol de Steiner es conectar estos terminales mediante un árbol cuyo peso sea lo más pequeño posible. Para transformar este problema en una instancia del problema del árbol de expansión k -mínimo, Ravi et al. (1996) adjuntan a cada terminal un árbol de aristas de peso cero con un gran número t de vértices por árbol. (Para un grafo con n vértices y r terminales, utilizan t = n − r − 1 vértices añadidos por árbol). Luego, piden el árbol de expansión k -mínimo en este grafo aumentado con k = rt . La única forma de incluir tantos vértices en un árbol de expansión k es utilizar al menos un vértice de cada árbol añadido, ya que no quedan suficientes vértices si se omite incluso uno de los árboles añadidos. Sin embargo, para esta elección de k , es posible que el árbol de expansión k incluya solo las aristas del grafo original necesarias para conectar todos los terminales. Por lo tanto, el árbol de expansión k -mínimo debe formarse combinando el árbol de Steiner óptimo con suficientes aristas de peso cero de los árboles añadidos para que el tamaño total del árbol sea suficientemente grande. ^{[ 2 ]}

Incluso para un grafo cuyos pesos de aristas pertenecen al conjunto {1, 2, 3 }, probar si el valor de la solución óptima es menor que un umbral dado es NP-completo . Sigue siendo NP-completo para grafos planares . La versión geométrica del problema también es NP-difícil, pero no se sabe que pertenezca a NP, debido a la dificultad de comparar sumas de raíces cuadradas; en cambio, pertenece a la clase de problemas reducibles a la teoría existencial de los reales . ^{[ 2 ]}

El árbol de expansión k -mínimo se puede encontrar en tiempo polinomial para grafos de ancho de árbol acotado y para grafos con solo dos pesos de arista distintos. ^{[ 2 ]}

Debido a la alta complejidad computacional de encontrar una solución óptima para el problema del árbol de expansión k -mínimo, gran parte de la investigación sobre este problema se ha concentrado en algoritmos de aproximación . El objetivo de dichos algoritmos es encontrar una solución aproximada en tiempo polinomial con una pequeña razón de aproximación . La razón de aproximación se define como la razón entre la longitud de la solución calculada y la longitud óptima para una instancia del peor caso, aquella que maximiza esta razón. Dado que la reducción de la NP-dureza para el problema del árbol de expansión k -mínimo conserva el peso de todas las soluciones, también conserva la dificultad de aproximación del problema. En particular, dado que el problema del árbol de Steiner es NP-difícil de aproximar con una razón de aproximación mejor que 96/95, ^{[ 3 ]} lo mismo ocurre con el problema del árbol de expansión k -mínimo.

La mejor aproximación conocida para el problema general alcanza una razón de aproximación de 2, y es la de Garg (2005) . ^{[ 4 ]} Esta aproximación se basa en gran medida en el esquema primal-dual de Goemans y Williamson (1992) . ^{[ 5 ]} Cuando la entrada consiste en puntos en el plano euclidiano (cualesquiera dos de los cuales pueden conectarse en el árbol con un costo igual a su distancia), existe un esquema de aproximación de tiempo polinomial ideado por Arora (1998) . ^{[ 6 ]}

• Árbol de expansión k mínimo en "Un compendio de problemas de optimización NP"
• KCTLIB , KCTLIB: una biblioteca para el problema del árbol de cardinalidad K ponderado por aristas.