LISTA DE PROBLEMAS

En la teoría de grafos , la métrica de la dimensión de un gráfico G es la cardinalidad mínima de un subconjunto S de vértices de tal manera que todos los otros vértices se determinan de forma única por sus distancias a los vértices en S . Encontrar la dimensión métrica de un gráfico es un problema NP-difícil ; La versión de decisión, que determina si la dimensión métrica es menor que un valor dado, es NP-completa .

Definición detallada [ editar ]

Para un subconjunto ordenado $${\ displaystyle W = \ {w_ {1}, w_ {2}, \ dots, w_ {k} \}}de vértices y un vértice v en un gráfico conectado G , la representación de v con respecto a W es la k -tupla ordenada$${\ displaystyle r (v | W) = (d (v, w_ {1}), d (v, w_ {2}), \ dots, d (v, w_ {k}))}, donde d ( x , y ) representa la distancia entre los vértices x e y . El conjunto W es un conjunto de resolución (o conjunto de localización) para G si cada dos vértices de G tienen representaciones distintas. La dimensión métrica de G es la cardinalidad mínima de un conjunto de resolución para G . Un conjunto resolver que contiene un número mínimo de vértices se llama una base (o conjunto de referencia) para G . Slater (1975) y Harary & Melter (1976) introdujeron conjuntos de resolución para gráficos de forma independiente ., mientras que el concepto de un conjunto de resolución y el de dimensión métrica fueron definidos mucho antes por Blumenthal en su monografía Theory and Applications of Distance Geometry . Los gráficos son ejemplos especiales de espacios métricos con su métrica de ruta intrínseca.

Árboles [ editar ]

Slater (1975) (ver también Harary & Melter (1976) y Khuller, Raghavachari & Rosenfeld (1996) ) proporciona la siguiente caracterización simple de la dimensión métrica de un árbol . Si el árbol es una ruta, su dimensión métrica es una. De lo contrario, deje que L denote el conjunto de vértices de grado uno en el árbol (generalmente llamados hojas, aunque Slater usa esa palabra de manera diferente). Sea K el conjunto de vértices que tienen un grado mayor que dos, y que están conectados por caminos de vértices de grado dos a una o más hojas. Entonces la dimensión métrica es | L | - | K |. Se puede formar una base de esta cardinalidad eliminando de Luna de las hojas asociadas con cada vértice en K . El mismo algoritmo es válido para el gráfico lineal del árbol, como lo demuestran Feng, Xu y Wang (2013) (y, por lo tanto, cualquier árbol y su gráfico lineal tienen la misma dimensión métrica).

Propiedades [ editar ]

En Chartrand et al. (2000) , se demuestra que:

• La dimensión métrica de un gráfico G es 1 si y solo si G es una ruta.
• La dimensión métrica de un gráfico n- vértice es n -1 si y solo si es un gráfico completo .
• La dimensión métrica de un gráfico de n -vértices es n - 2 si y solo si el gráfico es un gráfico bipartito completo K _s , t , un gráfico dividido $${\ displaystyle K_ {s} + {\ overline {K_ {t}}} (s \ geq 1, t \ geq 2)}o $${\ displaystyle K_ {s} + (K_ {1} \ cup K_ {t}) (s, t \ geq 1)}.

Relaciones entre el orden, la dimensión métrica y el diámetro [ editar ]

Khuller, Raghavachari y Rosenfeld (1996) prueban la desigualdad$${\ displaystyle n \ leq D ^ {\ beta} + \ beta}para cualquier gráfico n- vértice con diámetro D y dimensión métrica β. Este límite se deduce del hecho de que cada vértice que no está en el conjunto de resolución está determinado únicamente por un vector de distancia de longitud β con cada entrada siendo un número entero entre 1 y D (hay precisamente$${\ displaystyle D ^ {\ beta}}tales vectores). Sin embargo, el límite solo se logra para$${\ displaystyle D \ leq 3} o $${\ displaystyle \ beta = 1}; el límite más preciso$${\ displaystyle n \ leq \ left (\ lfloor 2D / 3 \ rfloor +1 \ right) ^ {\ beta} + \ beta \ sum _ {i = 1} ^ {\ lceil D / 3 \ rceil} (2i- 1) ^ {\ beta -1}} está demostrado por Hernando et al. (2010) .

Para clases de gráficos específicos, se pueden mantener límites más pequeños. Por ejemplo, Beaudou et al. (2018) demostró que$${\ displaystyle n \ leq (\ beta D + 4) (D + 2) / 8}para árboles (el límite es ajustado para valores pares de D ), y un límite de la forma$${\ displaystyle n = O (D ^ {2} \ beta)}para gráficos de plano externo . Los mismos autores probaron que$${\ displaystyle n \ leq (D \ beta +1) ^ {t-1}}para gráficos sin gráfico completo de orden t como menor y también dio límites para gráficos cordales y gráficos de ancho de árbol acotado . Los autores Foucaud et al. (2017a) límites comprobados de la forma$${\ displaystyle n = O (D \ beta ^ {2})}para gráficos de intervalos y gráficos de permutación , y límites de la forma$${\ displaystyle n = O (D \ beta)}para gráficos de intervalo de unidad, gráficos de permutación bipartita y cografías .

Complejidad computacional [ editar ]

Complejidad de decisión [ editar ]

Decidir si la dimensión métrica de un gráfico es como máximo un entero dado es NP-completo ( Garey & Johnson 1979 ). Queda NP-completo para el grado limitado grafos planos ( Díaz et al. 2012 ), gráficos de división , gráficos bipartitos y sus complementos , gráficos de líneas de grafos bipartitos ( Epstein, Levin y Woeginger 2012 ), gráficos de disco unidad ( Hoffmann & Wanke 2012 ), gráficos de intervalo de diámetro 2 y gráficos de permutación de diámetro 2 ( Foucaud et al. 2017b ).

Para cualquier constante constante k , las gráficas de dimensión métrica como máximo k pueden reconocerse en tiempo polinómico , probando todas las k -tuplas de vértices posibles , pero este algoritmo no es manejable con parámetros fijos (para el parámetro natural k , el tamaño de la solución ) Respondiendo a una pregunta planteada por Lokshtanov (2010) , Hartung y Nichterlein (2013) muestran que el problema de decisión de la dimensión métrica está completo para la clase de complejidad parametrizada W [2], lo que implica que un límite de tiempo de la forma n ^{O ( k )}tal como lo logra este algoritmo ingenuo es probablemente óptimo y es poco probable que exista un algoritmo manejable de parámetro fijo (para la parametrización por k ). Sin embargo, el problema se vuelve manejable con parámetros fijos cuando se restringe a gráficos de intervalos ( Foucaud et al. 2017b ), y más generalmente a gráficos de longitud de árbol acotada ( Belmonte et al. 2015 ), como gráficos cordales , gráficos de permutación o asteroidales. Gráficos triples libres.

Decidir si la dimensión métrica de un árbol es como máximo un entero dado se puede hacer en tiempo lineal ( Slater 1975 ; Harary & Melter 1976 ). Existen otros algoritmos en tiempo lineal para cographs ( Epstein, Levin y Woeginger 2012 ), gráficos de cadena ( Fernau et al. 2015 ) y gráficos de bloques de cactus ( Hoffmann, Elterman y Wanke 2016 ) (una clase incluyendo tanto los gráficos de cactus y gráficos de bloques ). El problema puede resolverse en tiempo polinómico en gráficos de plano externo ( Díaz et al. 2012 ). También se puede resolver en tiempo polinómico para gráficos de número ciclomático acotado( Epstein, Levin & Woeginger 2012 ), pero este algoritmo nuevamente no es manejable con parámetros fijos (para el parámetro "número ciclomático") porque el exponente en el polinomio depende del número ciclomático. Existen algoritmos manejables de parámetros fijos para resolver el problema de la dimensión métrica para los parámetros " cubierta de vértice " ( Hartung & Nichterlein 2013 ), "número máximo de hojas" ( Eppstein 2015 ) y "ancho modular" ( Belmonte et al. 2015 ). Los gráficos con número ciclomático acotado, número de cubierta de vértice o número máximo de hojas tienen ancho de árbol acotado , sin embargo, es un problema abierto para determinar la complejidad del problema de la dimensión métrica incluso en gráficos de ancho de árbol 2,gráficos paralelos en serie ( Belmonte et al. 2015 ).

Complejidad de aproximación [ editar ]

La dimensión métrica de un gráfico arbitrario de n -vértices se puede aproximar en tiempo polinómico a una relación de aproximación de$${\ displaystyle 2 \ log n}expresándolo como un problema de cobertura de conjunto , un problema de cubrir toda una colección de elementos dada por el menor número posible de conjuntos en una familia de conjuntos dada ( Khuller, Raghavachari y Rosenfeld 1996 ). En el problema de cobertura de conjunto formado a partir de un problema de dimensión métrica, los elementos a cubrir son los$${\ displaystyle {\ tbinom {n} {2}}}pares de vértices para distinguir, y los conjuntos que pueden cubrirlos son los conjuntos de pares que pueden distinguirse por un único vértice elegido. El límite de aproximación sigue luego aplicando algoritmos de aproximación estándar para la cobertura del conjunto. Un algoritmo codicioso alternativo que elige vértices de acuerdo con la diferencia de entropía entre las clases de equivalencia de los vectores de distancia antes y después de la elección logra una relación de aproximación aún mejor,$${\ displaystyle \ log n + \ log \ log _ {2} n + 1}( Hauptmann, Schmied y Viehmann 2012 ). Esta relación de aproximación es cercana a la mejor posible, ya que bajo los supuestos estándar de complejidad teórica, una relación de$${\ displaystyle (1- \ epsilon) \ log n} no se puede lograr en tiempo polinómico para ningún {\ displaystyle \ epsilon> 0}( Hauptmann, Schmied y Viehmann 2012 ). La última dureza de la aproximación aún se mantiene para casos restringidos a gráficos subcúbicos ( Hartung y Nichterlein 2013 ), e incluso a gráficos subcúbicos bipartitos como se muestra en la tesis doctoral de Hartung ( Hartung 2014 ).

En matemáticas, el corte mínimo de k es un problema de optimización combinatoria que requiere encontrar un conjunto de bordes cuya eliminación dividiría el gráfico en al menos k componentes conectados. Estos bordes se conocen como k -cut . El objetivo es encontrar el corte k de peso mínimo . Esta partición puede tener aplicaciones en diseño VLSI , minería de datos , elementos finitos y comunicación en computación paralela .

Definición formal [ editar ]

Dado un gráfico no dirigido G  = ( V ,  E ) con una asignación de pesos a los bordes w :  E  →  N y un número entero k  ∈ {2, 3,…, | V |}, la partición V en k conjuntos disjuntos F  = { C ₁ ,  C ₂ , ...,  C _k } mientras se minimiza

$${\ displaystyle \ sum _ {i = 1} ^ {k-1} \ sum _ {j = i + 1} ^ {k} \ sum _ {\ begin {smallmatrix} v_ {1} \ en C_ {i} \\ v_ {2} \ en C_ {j} \ end {smallmatrix}} w (\ left \ {v_ {1}, v_ {2} \ right \})}

Para una k fija , el problema es el tiempo polinómico solucionable en O (| V | ^k 2 ). ^[1] Sin embargo, el problema es NP-completo si k es parte de la entrada. ^[2] También es NP-completo si especificamos$${\ displaystyle k} vértices y pedir el mínimo $${\ displaystyle k}-cut que separa estos vértices entre cada uno de los conjuntos. ^[3]

Aproximaciones [ editar ]

Existen varios algoritmos de aproximación con una aproximación de 2 - 2 / k . Un algoritmo codicioso simple que logra este factor de aproximación calcula un corte mínimo en cada uno de los componentes conectados y elimina el más pesado. Este algoritmo requiere un total de n  - 1 cálculos de flujo máximo . Otro algoritmo que logra la misma garantía utiliza la representación del árbol Gomory – Hu de cortes mínimos. La construcción del árbol Gomory – Hu requiere n  - 1 cálculos de flujo máximo, pero el algoritmo requiere una O general ( kn) cálculos de flujo máximo. Sin embargo, es más fácil analizar el factor de aproximación del segundo algoritmo. ^[4] [5] Además, bajo la Hipótesis de Expansión del Conjunto Pequeño (una conjetura estrechamente relacionada con la Conjetura de los Juegos Únicos ), el problema es NP-difícil de aproximar dentro de$${\ displaystyle (2- \ epsilon)} factor para cada constante {\ displaystyle \ epsilon> 0}, ^[6] lo que significa que los algoritmos de aproximación mencionados anteriormente son esencialmente estrictos para grandes$${\ displaystyle k}.

Una variante del problema solicita un peso mínimo k -cut donde las particiones de salida tienen tamaños previamente especificados. Esta variante problemática es aproximada a un factor de 3 para cualquier k fijo si uno restringe la gráfica a un espacio métrico, lo que significa una gráfica completa que satisface la desigualdad del triángulo . ^[7] Más recientemente, se descubrieron esquemas de aproximación de tiempo polinomial (PTAS) para esos problemas.

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Árbol Steiner para tres puntos A , B y C (tenga en cuenta que no hay conexiones directas entre A , B , C ). El punto S de Steiner se encuentra en el punto Fermat del triángulo ABC .

Solución para cuatro puntos: hay dos puntos Steiner, S ₁ y S ₂

El problema del árbol Steiner , o problema mínimo del árbol Steiner , llamado así por Jakob Steiner , es un término general para una clase de problemas en la optimización combinatoria . Si bien los problemas del árbol Steiner pueden formularse en una serie de configuraciones, 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 los gráficos . Dado un gráfico no dirigido con pesos de borde no negativos y un subconjunto de vértices, generalmente conocidos como terminales, el problema del árbol Steiner en los gráficos requiere unárbol de peso mínimo que contiene todos los terminales (pero puede incluir vértices adicionales). Otras variantes conocidas son el problema del árbol Euclidean Steiner y el problema del árbol Steiner mínimo rectilíneo .

El problema del árbol de Steiner en los gráficos puede verse como una generalización de otros dos famosos problemas de optimización combinatoria: el problema del camino más corto (no negativo) y el problema del árbol de expansión mínima . Si un problema de árbol Steiner en gráficos contiene exactamente dos terminales, se reduce a encontrar la ruta más corta. Si, por otro lado, todos los vértices son terminales, el problema del árbol Steiner en los gráficos es equivalente al árbol de expansión mínima. Sin embargo, aunque tanto el camino más corto no negativo como el problema del árbol de expansión mínimo se pueden resolver en tiempo polinómico, la variante de decisión del problema del árbol de Steiner en los gráficos es NP-completa (lo que implica que la variante de optimización es NP-hard); de hecho, la variante de decisión se encontraba entre los 21 problemas originales de NP completos de Karp . El problema del árbol Steiner en los gráficos tiene aplicaciones en el diseño de circuitos o en el diseño de redes . Sin embargo, las aplicaciones prácticas generalmente requieren variaciones, dando lugar a una multitud de variantes del problema del árbol Steiner.

La mayoría de las versiones del problema del árbol Steiner son NP-hard , pero algunos casos restringidos pueden resolverse en tiempo polinómico . A pesar de la pesimista complejidad del peor de los casos, varias variantes del problema del árbol Steiner, incluido el problema del árbol Steiner en los gráficos y el problema del árbol Steiner rectilíneo, se pueden resolver de manera eficiente en la práctica, incluso para problemas del mundo real a gran escala.

Árbol Steiner euclidiano [ editar ]

Árboles Steiner mínimos de vértices de polígonos regulares con N = 3 a 8 lados. La longitud de red más baja L para N > 5 es la circunferencia menos un lado. Los cuadrados representan puntos Steiner.

El problema original se expresó en la forma que se conoce como el problema del árbol Steiner euclidiano o el problema del árbol Steiner geométrico : dados N puntos en el plano , el objetivo es conectarlos por líneas de longitud mínima total de tal manera que dos los puntos pueden estar interconectados por segmentos de línea directamente o por medio de otros puntos y segmentos de línea. Puede mostrarse que los segmentos de línea de conexión no se cruzan entre sí excepto en los puntos finales y forman un árbol, de ahí el nombre del problema.

El problema para N  = 3 se ha considerado durante mucho tiempo, y se extendió rápidamente al problema de encontrar una red estelar con un solo centro que se conecte a todos los N puntos dados, de longitud total mínima. Sin embargo, aunque el problema completo del árbol Steiner fue formulado en una carta de Gauss , su primer tratamiento serio fue en un artículo de 1934 escrito en checo por Vojtěch Jarník y Miloš Kössler  [ cs ] . Este documento se pasó por alto durante mucho tiempo, pero ya contiene "virtualmente todas las propiedades generales de los árboles Steiner" que luego se atribuyeron a otros investigadores, incluida la generalización del problema desde el avión a dimensiones superiores. ^[3]

Para el problema de Euclidean Steiner, los puntos agregados al gráfico ( puntos Steiner ) deben tener un grado de tres, y los tres bordes incidentes a dicho punto deben formar tres ángulos de 120 grados (ver punto Fermat ). Se deduce que el número máximo de puntos Steiner que puede tener un árbol Steiner es N  - 2, donde N es el número inicial de puntos dados.

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

Para el N general , el problema del árbol Euclidean Steiner es NP-duro y, por lo tanto, no se sabe si se puede encontrar una solución óptima utilizando un algoritmo de tiempo polinómico . Sin embargo, existe un esquema de aproximación de tiempo polinomial (PTAS) para árboles Euclidean Steiner, es decir, se puede encontrar una solución casi óptima en el tiempo polinomial. ^[4] No se sabe si el problema del árbol Euclidean Steiner es NP-completo, ya que no se conoce la pertenencia a la clase de complejidad NP.

Árbol Steiner rectilíneo [ editar ]

Artículo principal: árbol Steiner rectilíneo

El problema del árbol Steiner rectilíneo es una variante del problema del árbol 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 limitados por las reglas de diseño para ejecutarse solo en direcciones verticales y horizontales, por lo que el problema del árbol Steiner rectilíneo se puede utilizar para modelar el enrutamiento de redes con más de dos terminales. ^[5]

Árbol Steiner en gráficos y variantes [ editar ]

Los árboles Steiner se han estudiado ampliamente en el contexto de gráficos ponderados . El prototipo es, posiblemente, el problema del árbol Steiner en los gráficos . Sea G  = ( V ,  E ) un gráfico no dirigido con pesos de borde no negativos c y sea S  ⊆  V un subconjunto de vértices, llamados terminales . Un árbol de Steiner es un árbol en G que vanos S . Hay dos versiones del problema: en el problema de optimización asociado con los árboles Steiner, la tarea es encontrar un árbol Steiner de peso mínimo; en el problema de decisiónlos pesos de borde son enteros y la tarea es determinar si existe un árbol Steiner cuyo peso total no exceda un número natural predefinido k . El problema de decisión es uno de los 21 problemas completos de NP de Karp ; por lo tanto, el problema de optimización es NP-hard .

Un caso especial de este problema es cuando G es un gráfico completo , cada vértice v  ∈  V corresponde a un punto en un espacio métrico , y los pesos de los bordes w ( e ) para cada e  ∈  E corresponden a distancias en el espacio. Dicho de otro modo, los pesos de los bordes satisfacen la desigualdad del triángulo . Esta variante se conoce como el problema del árbol métrico de Steiner . Dada una instancia del problema del árbol Steiner (no métrico), podemos transformarlo en tiempo polinómico en una instancia equivalente del problema del árbol Steiner métrico; La transformación conserva el factor de aproximación. ^[6]

Si bien la versión euclidiana admite un PTAS, se sabe que el problema del árbol métrico de Steiner es APX completo , es decir, a menos que P = NP , es imposible lograr proporciones de aproximación que sean arbitrariamente cercanas a 1 en tiempo polinómico. Existe un algoritmo de tiempo polinómico que se aproxima al árbol mínimo de Steiner dentro de un factor de$${\ displaystyle \ ln (4) + \ varepsilon \ aprox 1.386}; ^[7] sin embargo, aproximándose dentro de un factor$${\ displaystyle 96/95 \ approx 1.0105}es NP-duro. ^[8] Para el caso restringido del problema Steiner Tree con distancias 1 y 2, se conoce un algoritmo de aproximación de 1.25. ^[9] Karpinski y Alexander Zelikovsky construyeron PTAS para los casos densos de problemas de Steiner Tree. ^[10]

En un caso especial del problema gráfico, el problema árbol de Steiner para gráficos cuasi-bipartito , S se requiere para incluir al menos un punto final de cada borde en G .

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

Otras generalizaciones del Árbol de Steiner son los k problema relacionado -Edge-Steiner red y el k problema de red conectada Steiner--vertex , donde el objetivo es encontrar un k gráfico -Edge-conectado o una k gráfico -vertex-conectado en vez que cualquier gráfico conectado.

El problema de Steiner también se ha planteado en la configuración general de espacios métricos y posiblemente para infinitos puntos. ^[12]

Aproximación al árbol Steiner [ editar ]

El problema general del árbol Steiner del gráfico se puede aproximar calculando el árbol de expansión mínimo del subgrafo del cierre métrico del gráfico inducido por los vértices terminales. El cierre métrica de un gráfico G es el grafo completo en el que cada borde se pondera por la distancia de la trayectoria más corta entre los nodos en G . Este algoritmo produce un árbol cuyo peso está dentro de un factor 2 - 2 / t del peso del árbol Steiner óptimo donde t es el número de hojas en el árbol Steiner óptimo; Esto se puede probar considerando un recorrido de vendedor ambulante en el árbol Steiner óptimo. La solución aproximada es computable en tiempo polinómico resolviendo primero el problema de los caminos más cortos de todos los parespara calcular el cierre métrico, luego resolviendo el problema del árbol de expansión mínimo .

Una serie de documentos proporcionó algoritmos de aproximación para el problema mínimo del árbol Steiner con relaciones de aproximación que mejoraron la relación 2 - 2 / t . Esta secuencia culminó con el algoritmo de Robins y Zelikovsky en 2000 que mejoró la relación a 1.55 al mejorar iterativamente el árbol de expansión terminal de costo mínimo. Más recientemente, sin embargo, Jaroslaw Byrka et al. resultó ser$${\ displaystyle \ ln (4) + \ varepsilon \ leq 1.39}aproximación utilizando una relajación de programación lineal y una técnica llamada redondeo aleatorio iterativo. ^[7]

Complejidad parametrizada del árbol Steiner [ editar ]

Se sabe que el problema del árbol Steiner del gráfico general es manejable con parámetros fijos , con el número de terminales como parámetro, por el algoritmo Dreyfus-Wagner. ^[13] [14] El tiempo de ejecución del algoritmo Dreyfus-Wagner es$${\ displaystyle 3 ^ {| S |} {\ text {poly}} (n)}, dónde $${\ displaystyle n} es el número de vértices del gráfico y $${\ displaystyle S}es el conjunto de terminales. Existen algoritmos más rápidos, ejecutándose en$${\ displaystyle c ^ {| S |} {\ text {poly}} (n)} tiempo para cualquier {\ displaystyle c> 2} o, en el caso de pesas pequeñas, $${\ displaystyle 2 ^ {| S |} {\ text {poly}} (n) W} tiempo, donde $${\ displaystyle W}es el peso máximo de cualquier borde. ^[15] [16] Una desventaja de los algoritmos mencionados anteriormente es que usan espacio exponencial ; existen algoritmos de espacio polinómico que se ejecutan en$${\ displaystyle 2 ^ {| S |} {\ text {poly}} (n) W} tiempo y $${\ displaystyle (7.97) ^ {| S |} {\ text {poly}} (n) \ log W}hora. ^[17] [18]

Se sabe que el problema del árbol Steiner de gráfico general no tiene un algoritmo parametrizado ejecutándose en $${\ displaystyle 2 ^ {\ epsilon t} {\ text {poly}} (n)} tiempo para cualquier {\ displaystyle \ epsilon <1 font="">, dónde $${\ displaystyle t}es el número de aristas del árbol Steiner óptimo, a menos que el problema de la cubierta del conjunto tenga un algoritmo ejecutándose en$${\ displaystyle 2 ^ {\ epsilon n} {\ text {poly}} (m)} tiempo para algunos {\ displaystyle \ epsilon <1 font="">, dónde $${\ displaystyle n} y $${\ displaystyle m}son el número de elementos y el número de conjuntos, respectivamente, de la instancia del problema de cobertura del conjunto. ^[19] Además, se sabe que el problema no admite un núcleo polinomial a menos que$${\ displaystyle {\ text {coNP}} \ subseteq {\ text {NP / poly}}}, incluso parametrizado por el número de bordes del árbol Steiner óptimo y si todos los pesos de los bordes son 1. ^[20]

Relación Steiner [ editar ]

La relación Steiner es el supremum de la relación entre la longitud total del árbol de expansión mínimo y el árbol Steiner mínimo para un conjunto de puntos en el plano euclidiano. ^[21]

En el problema del árbol Euclidiano de Steiner, se conjetura que la relación de Steiner es $${\ displaystyle {\ tfrac {2} {\ sqrt {3}}} \ aprox 1.1547}, la relación que se logra con tres puntos en un triángulo equilátero con un árbol de expansión que usa dos lados del triángulo y un árbol Steiner que conecta los puntos a través del centroide del triángulo. A pesar de las afirmaciones anteriores de una prueba, ^[22] la conjetura todavía está abierta. ^[23] El límite superior mejor aceptado para el problema es 1.2134, de Chung y Graham (1985) .

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