Problema del árbol de Steiner

En matemáticas combinatorias , el problema del árbol de Steiner , o problema del árbol de Steiner mínimo , llamado así en honor a Jakob Steiner , es un término general para una clase de problemas en optimización combinatoria . Si bien los problemas del árbol de Steiner pueden formularse en varios contextos, todos requieren una interconexión óptima para un conjunto dado de objetos y una función objetivo predefinida . Una variante bien conocida, que a menudo se usa como sinónimo del término problema del árbol de Steiner, es el problema del árbol de Steiner en grafos . Dado un grafo no dirigido con pesos de aristas no negativos y un subconjunto de vértices , generalmente denominados terminales, el problema del árbol de Steiner en grafos requiere un árbol de peso mínimo que contenga todos los terminales (pero puede incluir vértices adicionales) y minimice el peso total de sus aristas. Otras variantes bien conocidas son el problema del árbol de Steiner euclidiano y el problema del árbol de Steiner mínimo rectilíneo .

El problema del árbol de Steiner en grafos puede considerarse una generalización de otros dos problemas de optimización combinatoria famosos: el problema del camino más corto (no negativo) y el problema del árbol de expansión mínima . Si un problema del árbol de Steiner en grafos contiene exactamente dos terminales, se reduce a encontrar el camino más corto. Si, por otro lado, todos los vértices son terminales, el problema del árbol de Steiner en grafos es equivalente al problema del árbol de expansión mínima. Sin embargo, mientras que tanto el problema del camino más corto no negativo como el del árbol de expansión mínima se pueden resolver en tiempo polinomial , no se conoce ninguna solución para el problema del árbol de Steiner. Su variante de decisión , que pregunta si una entrada dada tiene un árbol con un peso menor que un umbral dado, es NP-completa , lo que implica que la variante de optimización, que pregunta por el árbol de peso mínimo en un grafo dado, es NP-difícil . De hecho, la variante de decisión estaba entre los 21 problemas NP-completos originales de Karp . El problema del árbol de Steiner en grafos tiene aplicaciones en el diseño de circuitos o redes . Sin embargo, las aplicaciones prácticas suelen requerir variaciones, lo que da lugar a multitud de variantes del problema del árbol de Steiner.

La mayoría de las versiones del problema del árbol de Steiner son NP-difíciles, pero algunos casos restringidos pueden resolverse en tiempo polinomial. A pesar de la complejidad pesimista en el peor de los casos , varias variantes del problema del árbol de Steiner, incluyendo el problema del árbol de Steiner en grafos y el problema del árbol de Steiner rectilíneo, pueden resolverse eficientemente en la práctica, incluso para problemas del mundo real a gran escala. ^{[ 1 ] [ 2 ]}

El problema original se planteó de la forma que se conoce como el problema del árbol de Steiner euclidiano o problema del árbol de Steiner geométrico : dados N puntos en el plano , el objetivo es conectarlos mediante líneas de longitud total mínima de tal manera que cualesquiera dos puntos puedan interconectarse mediante segmentos de línea, ya sea directamente o a través de otros puntos y segmentos de línea.

Aunque el problema lleva el nombre de Steiner, fue planteado por primera vez en 1811 por Joseph Diez Gergonne en la siguiente forma: «Varias ciudades están ubicadas en lugares conocidos en un plano; el problema consiste en conectarlas mediante un sistema de canales cuya longitud total sea lo más pequeña posible». ^{[ 3 ]}

Se puede demostrar que los segmentos de línea que los conectan no se intersecan entre sí excepto en los puntos extremos y forman un árbol, de ahí el nombre del problema.

El problema para N  =  3 se ha considerado durante mucho tiempo y rápidamente se extendió al problema de encontrar una red en estrella con un único nodo que conecte todos los N puntos dados, de longitud total mínima. Sin embargo, aunque el problema completo del árbol de Steiner fue formulado en una carta por Gauss , su primer tratamiento serio se dio en un artículo de 1934 escrito en checo por Vojtěch Jarník y Miloš Kössler . Este artículo fue ignorado durante mucho tiempo, pero ya contiene "prácticamente todas las propiedades generales de los árboles de Steiner" que posteriormente se atribuyeron a otros investigadores, incluida la generalización del problema del plano a dimensiones superiores. ^{[ 4 ]}

Para el problema euclidiano de Steiner, los puntos añadidos al grafo ( puntos de Steiner ) deben tener un grado de tres, y las tres aristas incidentes a dicho punto deben formar tres ángulos de 120 grados (véase el punto de Fermat ). Por consiguiente, el número máximo de puntos de Steiner que puede tener un árbol de Steiner es N − 2   , donde N es el número inicial de puntos dados. (Todas estas propiedades ya fueron establecidas por Gergonne ).

Para N = 3 hay dos casos posibles: si el triángulo formado por los puntos dados tiene todos los ángulos menores de 120 grados, la solución viene dada por un punto de Steiner situado en el punto de Fermat ; de lo contrario, la solución viene dada por los dos lados del triángulo que se encuentran en un ángulo de 120 grados o más.

Para N general , el problema del árbol de Steiner euclidiano es NP-difícil , por lo que se desconoce si se puede encontrar una solución óptima mediante un algoritmo de tiempo polinomial . Sin embargo, existe un esquema de aproximación de tiempo polinomial (PTAS) para árboles de Steiner euclidianos, es decir, se puede encontrar una solución casi óptima en tiempo polinomial. ^{[ 5 ]} Se desconoce si el problema del árbol de Steiner euclidiano es NP-completo, ya que se desconoce si pertenece a la clase de complejidad NP.

El problema del árbol de Steiner rectilíneo es una variante del problema del árbol de Steiner geométrico en el plano, en el que la distancia euclidiana se reemplaza por la distancia rectilínea . El problema surge en el diseño físico de la automatización del diseño electrónico . En los circuitos VLSI , el enrutamiento de cables se realiza mediante cables que a menudo están restringidos por reglas de diseño a correr solo en direcciones vertical y horizontal, por lo que el problema del árbol de Steiner rectilíneo se puede utilizar para modelar el enrutamiento de redes con más de dos terminales. ^{[ 6 ]}

Los árboles de Steiner se han estudiado ampliamente en el contexto de los grafos ponderados . El prototipo es, posiblemente, el problema del árbol de Steiner en grafos . Sea G  =  ( V , E )  un grafo no dirigido con pesos de arista no negativos c y sea S  ⊆ V  un subconjunto de vértices, llamados terminales . Un árbol de Steiner es un árbol en G que abarca S. Hay dos versiones del problema: en el problema de optimización asociado con los árboles de Steiner, la tarea es encontrar un árbol de Steiner de peso mínimo; en el problema de decisión , los pesos de las aristas son enteros y la tarea es determinar si existe un árbol de Steiner cuyo peso total no exceda un número natural predefinido k . El problema de decisión es uno de los 21 problemas NP-completos de Karp ; por lo tanto, el problema de optimización es NP-difícil . Los problemas de árboles de Steiner en grafos se aplican a diversos problemas en investigación e industria, ^{[ 7 ]} incluyendo el enrutamiento de multidifusión ^{[ 8 ]} y la bioinformática. ^{[ 9 ]}

Un caso especial de este problema se da cuando G es un grafo completo , cada vértice v  ∈ V  corresponde a un punto en un espacio métrico , y los pesos de las aristas w ( e ) para cada e  ∈ E corresponden a distancias en el espacio. Dicho de otro modo, los pesos de las aristas satisfacen la desigualdad triangular . Esta variante se conoce como el problema del árbol de Steiner métrico . Dada una instancia del problema del árbol de Steiner (no métrico), podemos transformarla en tiempo polinomial en una instancia equivalente del problema del árbol de Steiner métrico; la transformación conserva el factor de aproximación. ^{[ 10 ]} 

Si bien la versión euclidiana admite un PTAS, se sabe que el problema del árbol de Steiner métrico es APX-completo , es decir, a menos que P = NP , es imposible lograr razones de aproximación que sean arbitrariamente cercanas a 1 en tiempo polinomial. Existe un algoritmo de tiempo polinomial que aproxima el árbol de Steiner mínimo con un factor de${\displaystyle \ln(4)+\varepsilon \approx 1.386}$; ^{[ 11 ]} sin embargo, aproximando dentro de un factor${\displaystyle 96/95\approx 1.0105}$es NP-difícil. ^{[ 12 ]} Para el caso restringido del problema del árbol de Steiner con distancias 1 y 2, se conoce un algoritmo de aproximación de 1,25. ^{[ 13 ]} Karpinski y Alexander Zelikovsky construyeron PTAS para las instancias densas de problemas de árboles de Steiner. ^{[ 14 ]}

En un caso especial del problema de grafos, el problema del árbol de Steiner para grafos cuasi-bipartitos , se requiere que S incluya al menos un extremo de cada arista en G.

El problema del árbol de Steiner también se ha investigado en dimensiones superiores y en diversas superficies. Se han encontrado algoritmos para hallar el árbol mínimo de Steiner en la esfera, el toro, el plano proyectivo , los conos anchos y estrechos, entre otros. ^{[ 15 ]}

Otras generalizaciones del problema del árbol de Steiner son el problema de la red de Steiner k -aristas-conectada y el problema de la red de Steiner k -vértices-conectada , donde el objetivo es encontrar un grafo k -aristas-conectado o un grafo k -vértices-conectado en lugar de cualquier grafo conectado. Otra generalización bien estudiada ^{[ 16 ]} es el problema de diseño de redes supervivientes (SNDP), donde la tarea es conectar cada par de vértices con un número dado (posiblemente 0) de caminos disjuntos por aristas o vértices.

El problema de Steiner también se ha planteado en el contexto general de espacios métricos y para un número posiblemente infinito de puntos. ^{[ 17 ]}

El problema general del árbol de Steiner en grafos se puede aproximar calculando el árbol de expansión mínimo del subgrafo del cierre métrico del grafo inducido por los vértices terminales, como se publicó por primera vez en 1981 por Kou et al. ^{[ 18 ]} El cierre métrico de un grafo${\displaystyle G}$es el grafo completo en el que cada arista está ponderada por la distancia del camino más corto entre los nodos en${\displaystyle G}$. Este algoritmo produce un árbol cuyo peso está dentro de un${\displaystyle 2-2/t}$factor del peso del árbol de Steiner óptimo donde${\displaystyle t}$es el número de hojas en el árbol de Steiner óptimo; esto se puede demostrar considerando un recorrido del viajante de comercio en el árbol de Steiner óptimo. Esta solución aproximada es computable en${\displaystyle O(|S||V|^{2})}$tiempo polinomial resolviendo primero el problema de los caminos más cortos entre todos los pares para calcular el cierre métrico, y luego resolviendo el problema del árbol de expansión mínima .

Otro algoritmo popular para aproximar el árbol de Steiner en grafos fue publicado por Takahashi y Matsuyama en 1980. ^{[ 19 ]} Su solución construye incrementalmente el árbol de Steiner comenzando desde un vértice arbitrario y agregando repetidamente el camino más corto desde el árbol hasta el vértice más cercano en${\displaystyle S}$que aún no se ha añadido. Este algoritmo también tiene${\displaystyle O(|S||V|^{2})}$tiempo de ejecución y produce un árbol cuyo peso está dentro${\displaystyle 2-2/|S|}$de óptimo.

En 1986, Wu et al. ^{[ 20 ]} mejoraron drásticamente el tiempo de ejecución evitando el preprocesamiento de los caminos más cortos entre todos los pares. En cambio, adoptan un enfoque similar al algoritmo de Kruskal para calcular un árbol de expansión mínima, comenzando desde un bosque de${\displaystyle |S|}$árboles disjuntos, y "creciéndolos" simultáneamente usando una búsqueda en anchura similar al algoritmo de Dijkstra pero comenzando desde múltiples vértices iniciales. Cuando la búsqueda encuentra un vértice que no pertenece al árbol actual, los dos árboles se fusionan en uno. Este proceso se repite hasta que solo queda un árbol. Al usar un montículo (estructura de datos) para implementar la cola de prioridad y una estructura de datos de conjunto disjunto para rastrear a qué árbol pertenece cada vértice visitado, este algoritmo logra${\displaystyle O(|E|\log |V|)}$tiempo de ejecución, aunque no mejora el${\displaystyle 2-2/t}$relación de costos de Kou et al.

Una serie de artículos proporcionaron algoritmos de aproximación para el problema del árbol de Steiner mínimo con razones de aproximación que mejoraron con respecto a los anteriores.${\displaystyle 2-2/t}$relación. Esta secuencia culminó con el algoritmo de Robins y Zelikovsky en 2000, que mejoró la relación a 1,55 mediante la mejora iterativa del árbol de expansión terminal de costo mínimo. ^{[ 21 ]} Sin embargo, más recientemente, Byrka et al. demostraron una${\displaystyle \ln(4)+\varepsilon \leq 1.39}$aproximación mediante una relajación de programación lineal y una técnica denominada redondeo aleatorio iterativo. ^{[ 11 ]}

Se sabe que el problema general del árbol de Steiner gráfico es tratable con parámetros fijos , con el número de terminales como parámetro, mediante el algoritmo de Dreyfus-Wagner. ^{[ 22 ] [ 23 ]} El tiempo de ejecución del algoritmo de Dreyfus-Wagner es${\displaystyle 3^{|S|}{\text{poly}}(n)}$donde n es el número de vértices del grafo y S es el conjunto de terminales. Existen algoritmos más rápidos que se ejecutan en${\displaystyle c^{|S|}{\text{poly}}(n)}$tiempo para cualquier${\displaystyle c>2}$o, en el caso de pesos pequeños,${\displaystyle 2^{|S|}{\text{poly}}(n)W}$tiempo, donde W es el peso máximo de cualquier arista. ^{[ 24 ] [ 25 ]} Una desventaja de los algoritmos mencionados anteriormente es que utilizan espacio exponencial ; existen algoritmos de espacio polinomial que se ejecutan en${\displaystyle 2^{|S|}{\text{poly}}(n)W}$tiempo y${\displaystyle (7.97)^{|S|}{\text{poly}}(n)\log W}$tiempo. ^{[ 26 ] [ 27 ]}

Se sabe que el problema general del árbol de Steiner en grafos no tiene un algoritmo parametrizado que se ejecute en${\displaystyle 2^{\epsilon t}{\text{poly}}(n)}$tiempo para cualquier${\displaystyle \epsilon <1}$, donde t es el número de aristas del árbol de Steiner óptimo, a menos que el problema de cobertura de conjuntos tenga un algoritmo ejecutándose en${\displaystyle 2^{\epsilon n}{\text{poly}}(m)}$tiempo para algunos${\displaystyle \epsilon <1}$donde n y m son el número de elementos y el número de conjuntos, respectivamente, de la instancia del problema de cobertura de conjuntos. ^{[ 28 ]} Además, se sabe que el problema no admite un núcleo polinomial a menos que${\displaystyle {\textsf {coNP}}\subseteq {\textsf {NP/poly}}}$, incluso parametrizado por el número de aristas del árbol de Steiner óptimo y si todos los pesos de las aristas son 1. ^{[ 29 ]}

Si bien el problema del árbol de Steiner gráfico no admite un núcleo polinomial a menos que${\displaystyle {\textsf {coNP}}\subseteq {\textsf {NP/poly}}}$Parametrizado por el número de terminales, admite un esquema de kernelización aproximada de tamaño polinomial (PSAKS): para cualquier${\displaystyle \varepsilon >0}$es posible calcular un núcleo de tamaño polinomial, que solo pierde un${\displaystyle 1+\varepsilon }$factor en la calidad de la solución. ^{[ 30 ]}

Al parametrizar el problema del árbol de Steiner gráfico por el número p de no terminales (vértices de Steiner) en la solución óptima, el problema es W[1]-difícil (a diferencia de la parametrización por el número de terminales, como se mencionó anteriormente). Al mismo tiempo, el problema es APX-completo y, por lo tanto, no admite un PTAS , a menos que P = NP . Sin embargo, existe un esquema de aproximación parametrizado que para cualquier${\displaystyle \varepsilon >0}$calcula un${\displaystyle (1+\varepsilon )}$-aproximación en${\displaystyle 2^{O(p^{2}/\varepsilon ^{4})}n^{O(1)}}$tiempo. ^{[ 31 ]} También existe un PSAKS para esta parametrización. ^{[ 31 ]}

La razón de Steiner es el supremo de la razón entre la longitud total del árbol de expansión mínimo y el árbol de Steiner mínimo para un conjunto de puntos en el plano euclidiano. ^{[ 32 ]}

En el problema del árbol de Steiner euclidiano, la conjetura de Gilbert-Pollak es que la razón de Steiner es${\displaystyle {\tfrac {2}{\sqrt {3}}}\approx 1.1547}$, la razón que se obtiene con tres puntos en un triángulo equilátero con un árbol de expansión que utiliza dos lados del triángulo y un árbol de Steiner que conecta los puntos a través del centroide del triángulo. A pesar de afirmaciones anteriores de una demostración, ^{[ 33 ]} la conjetura sigue abierta. ^{[ 34 ]} La mejor cota superior ampliamente aceptada para el problema es 1,2134, por Chung y Graham (1985) .

Para el problema del árbol de Steiner rectilíneo, la razón de Steiner es exactamente${\displaystyle {\tfrac {3}{2}}}$, la proporción que se logra mediante cuatro puntos en un cuadrado con un árbol de expansión que utiliza tres lados del cuadrado y un árbol de Steiner que conecta los puntos a través del centro del cuadrado. ^{[ 35 ]} Más precisamente, para${\displaystyle L_{1}}$distancia en la que se debe inclinar el cuadrado${\displaystyle 45^{\circ }}$con respecto a los ejes de coordenadas, mientras que para${\displaystyle L_{\infty }}$distancia a la que el cuadrado debe estar alineado con el eje.

• Problema del bosque opaco
• El problema del viajante
• Conector Wiener

• GeoSteiner (Software para resolver problemas de árboles de Steiner euclidianos y rectilíneos; código fuente disponible, gratuito para uso no comercial)
• SCIP-Jack (Software para resolver el problema del árbol de Steiner en grafos y 14 variantes, por ejemplo, el problema del árbol de Steiner con recolección de premios; gratuito para uso no comercial)
• Subrutina en Fortran para encontrar el vértice de Steiner de un triángulo (es decir, el punto de Fermat ), sus distancias a los vértices del triángulo y los pesos relativos de los vértices.
• Phylomurka (Solucionador para problemas de árboles de Steiner a pequeña escala en grafos)
• https://www.youtube.com/watch?v=PI6rAOWu-Og (Vídeo: cómo resolver el problema del árbol de Steiner con agua y jabón)
• Noormohammadpour, Mohammad; Raghavendra, Cauligi S.; Rao, Sriram; Kandula, Srikanth (2017), "Uso de árboles de Steiner para minimizar los tiempos promedio de finalización de transferencias masivas de datos", DCCast: Transferencias eficientes de punto a multipunto a través de centros de datos , USENIX Association, arXiv : 1707.02096
• Hazewinkel, M. (2001) [1994], "Problema del árbol de Steiner" , Enciclopedia de Matemáticas , EMS Press
• M. Hauptmann, M. Karpinski (2013): Un compendio sobre problemas de árboles de Steiner