Problema da árvore de Steiner

Na Combinatória, o problema da árvore de Steiner, problema da autoestrada, ou problema da árvore mínima de Steiner, denominado em referência a Jakob Steiner, é um termo genérico para uma classe de problemas na otimização combinatória. Uma variante bastante conhecida, que é geralmente utilizada como sinônimo do termo problema da árvore de Steiner, é o problema da árvore de Steiner em grafos. Dado um grafo simples com os pesos das arestas não negativas e um subconjunto de vértices, geralmente referidos como terminais, o problema da árvore de Steiner em grafos requer uma árvore com menor peso que contenha todos os terminais (mas poderá incluir vértices adicionais) e minimiza o total dos pesos de suas arestas. Outras variantes bastante conhecidas são o problema da árvore de Steiner Euclidiana e o problema da árvore de Steiner retilinear.

O problema da árvore de Steiner em grafos pode ser visto como uma generalização de dois outros problemas: o problema do caminho mínimo (não negativo) e o problema da árvore de extensão mínima. Se um problema da árvore de Steiner em grafos contém exatamente dois terminais, a procura se restringe ao caminho mínimo. Se, por outro lado, todos os vértices são terminais, o problema da árvore de Steiner em grafos é equivalente à árvore de extensão mínima. No entanto, por mais que o problema do caminho mínimo não negativo e da árvore de extensão mínima são resolvidos em tempo polinomial, nenhuma solução do tipo é conhecida para o problema da árvore de Steiner em grafos. Sua variante de decisão, em que se pergunta se uma determinada entrada tem uma árvore de peso menor que um determinado limite, é NP-completa, o que implica que a variante de otimização, pedindo pela árvore de peso mínimo num dado grafo, é NP-difícil. Na verdade, um deles estava entre os 21 problemas originais NP-completos de Karp. O problema da árvore de Steiner em grafos tem aplicações em layout de circuito ou em design de rede. No entanto, aplicações práticas geralmente requerem variações, o que aumenta a quantidade de variantes do problema da árvore de Steiner.

A maioria das versões do problema da árvore de Steiner são NP-difíceis, mas alguns casos restritos podem ser resolvidos em tempo polinomial. Apesar do pessimismo da complexidade de pior caso, diversas variantes do problema da árvore de Steiner, incluindo o problema da árvore de Steiner em grafos e problema da árvore de Steiner retilinear, podem ser resolvidos eficientemente na prática, mesmo para problemas do mundo real em larga escala.^[1][2]

O problema original foi enunciado na forma em que se tornou conhecido como o problema da árvore de Steiner euclidiana ou problema geométrico da árvore de Steiner: Dados N pontos em um plano, o objetivo é conectá-los por linhas de comprimento total mínimo de tal forma que quaisquer dois pontos podem ser interligados por segmentos de reta diretamente ou através de outros pontos e segmentos de reta. Pode ser mostrado que os segmentos de reta não se cruzam uns aos outros, exceto nas extremidades e formam uma árvore, daí o nome do problema.

O problema para N = 3 tem sido estudado há muito tempo e rapidamente se estendeu ao problema de encontrar uma rede estelar com um único centro conectando todos os N pontos dados, com o comprimento total mínimo. No entanto, embora o problema completo da árvore de Steiner tenha sido formulado em uma carta por Gauss, seu primeiro tratamento sério foi em um artigo de 1934 escrito em tcheco por Vojtěch Jarník e Miloš Kössler. Este artigo foi muito ignorado, mas já continha "virtualmente todas as propriedades gerais das árvores de Steiner" posteriormente atribuídas a outros pesquisadores, incluindo a generalização do problema do plano para dimensões maiores.^[3]

Para o problema da árvore de Steiner euclidiana, pontos adicionados ao grafo (pontos de Steiner) devem ter um grau 3, e as três arestas incidentes ao ponto devem formar 3 ângulos de 120 graus (ver ponto de Fermat). Segue que o número máximo de pontos que uma árvore de Steiner pode ter é N - 2, em que N é o número de pontos inicialmente dados.

Para N = 3, existem dois casos possíveis: se o triângulo formado pelos pontos dados tem todos os ângulos que são menores do que 120 graus, a solução é dada por um ponto de Steiner localizado no ponto de Fermat; caso contrário, a solução é dada pelos dois lados do triângulo, que se encontram no ângulo igual ou maior que 120 graus.

Para N geral, o problema da árvore euclidiana de Steiner é NP-difícil, e, portanto, não se sabe se uma solução ótima pode ser encontrada por meio de um algoritmo de tempo polinomial. No entanto, existe um esquema de aproximação de tempo polinomial (PTAS) para árvores de Steiner euclidiana, isto é, uma solução quase ótima pode ser encontrada em tempo polinomial.^[4] Não se sabe se o problema da árvore de Steiner euclidiana é NP-completo, uma vez que a sua pertinência à classe de complexidade NP não é conhecida.

O problema mínimo da árvore de Steiner retilinear é uma variante do problema geométrico da árvore de Steiner no plano, no qual a distância euclidiana é substituído pela distância retilínea. O problema surge na concepção física de automação de design eletrônico. Em circuitos de VLSI, a distribuição de fios é realizada por fios que são muitas vezes restringidos pelas regras de design para percorrer somente em direções verticais e horizontais, de modo que o problema da árvore retilínea de Steiner pode ser utilizado para modelar o roteamento de redes com mais do que dois terminais.^[5]

As árvores de Steiner também foram estudadas no contexto de grafos com peso. O protótipo é, sem dúvida, o problema da árvore de Steiner em grafos. Seja G = (V, E) um grafo não direcionado como vértices não negativos de peso c e um subconjunto S ⊆ V de vértices, chamados de terminais. Uma árvore de Steiner é uma árvore no grafo G que abrange todos os vértices de S. Existem duas versões do problema: no problema de otimização associado com árvores de Steiner, a tarefa é encontrar uma árvore de Steiner de peso mínimo; no problema de decisão, os pesos das arestas são inteiros e a tarefa é determinar se exite uma árvore de Steiner que de peso total no máximo k existe. O problema da decisão foi um dos 21 problemas NP-completos de Karp; daí o problema de otimização é NP-difícil. Os problemas da árvore de Steiner em grafos são aplicadoa a varios problemas de empresa e industria,^[6] incluindo roteamento multicast^[7] e bioinformática.^[8]

Um caso especial deste problema é quando G é um grafo completo, cada vértice v ∈ V corresponde a um ponto em um espaço métrico, e os pesos das arestas w(e) para cada e ∈ E correspondem às distâncias no espaço. Em outras palavras, os pesos das arestas satisfazem a desigualdade triangular. Esta variante é conhecida como o problema da árvore de Steiner métrico. Dada uma instância (não-métrica) do problema da árvore de Steiner, podemos transformá-la em tempo polinomial em uma instância equivalente do problema métrico da árvore de Steiner; a transformação preserva o fator de aproximação.^[9]

Embora a versão euclidiana admita um PTAS, sabe-se que o problema métrico da árvore de Steiner é APX-completo, isto é, a menos que P = NP, é impossível de alcançar proporções de aproximação que são arbitrariamente próximas de 1 em tempo polinomial. Há um algoritmo de tempo polinomial que aproxima a árvore mínima de Steiner dentro de um fator de ln(4) + ϵ ≈ 1.386;^[10] No entanto, a aproximação dentro de um fator de 96/95 ≈ 1.0105 é NP-difícil.^[11] Para o caso restrito do problema da árvore de Steiner com distâncias 1 e 2, um algoritmo de aproximação com fator 1,25 é conhecido.^[12] Karpinski e Alexander Zelikovsky construiram um PTAS para as instâncias densas do problema da árvore de Steiner.^[13]

Em um caso especial do problema de grafo, o problema da árvore de Steiner para gratos quase-bipartidos, S tem que incluir pelo menos uma extremidade de cada aresta de G.

O problema da árvore de Steiner também tem sido investigado em dimensões mais elevadas e em várias superfícies. Algoritmos para encontrar a árvore mínima de Steiner tem sido encontrados na esfera, toro, plano projetivo, cones largos e estreitos, e outros.^[14]

Outras generalizações do problema da árvore de Steiner são o problema de k-arestas-conexo da rede de Steiner e o problema de k-vértices-conexos da rede de Steiner, no qual o objetivo é encontrar um grafo k-aresta-conexo ou um grafo k-vértice-conexo em vez do que grafo conexo qualquer. Outra generalização bastante estudada é o problema de projeto de redes sobrevivível, em que o objetivo é conectar cada par de vértices com um dado número (possivelmente 0) de caminhos de arestas ou vértices disjuntos.^[15]

O problema de Steiner também foi enunciado na definição geral dos espaços métricos e possivelmente para uma quantidade infinita de pontos.^[16]

O problema geral de grafo da árvore de Steiner pode ser aproximado computando a árvore geradora mínima do subgrafo do fecho métrico do grafo induzido pelos vértices terminais, conforme publicado pela primeira vez por Kou et al. em 1981.^[17] O fecho métrico de um grafo G é o grafo completo no qual cada aresta é ponderada pela distância do caminho mais curto entre os nós em G. Esse algoritmo produz uma árvore cujo peso está dentro de um fator de 2 - 2/t do peso da árvore de Steiner ótima em que t é o número de folhas na árvore de Steiner ótima; isso pode ser provado considerando o passeio do caixeiro-viajante na árvore de Steiner ótima. Uma solução aproximada é computável em tempo polinomial ${\displaystyle O(|S||V|^{2})}$ ao resolver primeiramente o problema dos caminhos mais curtos de todos os pares para computar o fecho métrico, e depois resolvendo o problema da árvore de extensão mínima.

Outro algoritmo popular para aproximar a árvore de Steiner em grafos foi publicado por Takahashi e Matsuyama em 1980.^[18] A solução deles constrói incrementalmente a árvore de Steiner, começando a partir de um vértice arbitrário e adicionando repetidamente o caminho mais curto da árvore para o vértice mais próximo em S que ainda não foi adicionado. Esse algoritmo também tem um tempo de execução de ${\displaystyle O(|S||V|^{2})}$ e produz uma árvore cujo peso está dentro de ${\displaystyle 2-{\frac {2}{|S|}}}$ do ótimo.

Em 1986, Wu et al.^[19] melhoraram drasticamente o tempo de execução, evitando o pré-cálculo dos caminhos mais curtos entre todos os pares de vértices. Em vez disso, eles adotaram uma abordagem semelhante à do algoritmo de Kruskal para calcular uma árvore geradora mínima, começando com uma floresta de |S| árvores disjuntas e "crescendo" simultaneamente usando uma busca em largura que se assemelha ao algoritmo de Dijkstra, mas começando a partir de múltiplos vértices iniciais. Quando a busca encontra um vértice que não pertence à árvore atual, as duas árvores são mescladas em uma. Esse processo é repetido até que reste apenas uma árvore. Usando uma estrutura de heap para implementar a fila de prioridade e uma estrutura de dados união-busca para rastrear a qual árvore pertence cada vértice visitado, esse algoritmo alcança um tempo de execução de ${\displaystyle O(|E|\log |V|)}$, embora não melhore a proporção de custo ${\displaystyle 2-{\frac {2}{t}}}$ de Kou et al.

Uma série de artigos forneceu algoritmos de aproximação para o problema da árvore de Steiner mínima com proporções de aproximação que melhorou a proporção de 2 - 2/t. A sequência culminou com o algoritmo de Robins e Zelikovsky em 2000, que melhorou esta proporção para 1,55 ao melhorar iterativamente a árvore geradora terminal de custo mínimo.^[20] Mais recentemente, entretanto, Byrka et al. provou uma aproximação de ln(4) + ϵ ≤ 1.39 usando um relaxamento da programação linear e uma técnica chamada de arredondamento randomizado, iterativo.^[10]

O problema geral da árvore de Steiner em grafos é conhecido por ser tratável em parâmetro fixo, com o número de terminais como um parâmetro, pelo algoritmo de Dreyfus-Wagner.^[21][22] O tempo de execução do algoritmo de Dreyfus-Wagner é ${\displaystyle 3^{|S|}{\text{poly}}(n)}$, em que n é o número de vértices do grafo e S o conjunto de terminais. Algoritmos mais rápidos existem, executando em tempo ${\displaystyle c^{|S|}{\text{poly}}(n)}$ para qualquer c > 2 ou, no caso de pesos baixos, tempo ${\displaystyle 2^{|S|}{\text{poly}}(n)W}$, em que W é o peso máximo de qualquer aresta.^[23][24] Uma desvantagem dos algoritmos mencionados anteriormente é que eles usam espaço exponencial [en]; existem algoritmos em espaço polinomial, que executa em tempo ${\displaystyle 2^{|S|}{\text{poly}}(n)W}$ e tempo ${\displaystyle (7.97)^{|S|}{\text{poly}}(n)\log W}$.^[25][26]

Sabe-se que o problema geral da árvore de Steiner em grafos não tem um algoritmo parametrizado que execute em tempo ${\displaystyle 2^{\epsilon t}{\text{poly}}(n)}$ para qualquer ϵ < 1, em que t é o número de arestas da árvore de Steiner ótima, exceto se o problema de cobertura de conjuntos tenha um algoritmo que execute em tempo ${\displaystyle 2^{\epsilon n}{\text{poly}}(m)}$ para algum ϵ < 1, em que n é o número de elementos e ${\displaystyle m}$ o número de conjuntos da instância do problema de cobertura de conjuntos.^[27] Além disso, sabe-se que o problema não admite um núcleo polinomial, exceto se ${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$, mesmo parametrizado pelo número de arestas de uma árvore de Steiner ótima e o peso de todas as arestas seja 1.^[28]

A proporção de Steiner é o supremo da razão entre o tamanho total da árvore geradora mínima para a árvore mínima de Steiner de um conjunto de pontos no plano euclidiano.^[29]

No problema da árvore euclidiana de Steiner, a proporção de Steiner é conjecturada a ser ${\displaystyle {\frac {2}{\sqrt {3}}}}$. Apesar das alegações anteriores de uma prova,^[30] a conjectura ainda está em aberto.^[31] O limite superior mais amplamente aceito para o problema é 1,2134, por Chung e Graham em 1985.^[32]

No problema da árvore de Steiner retilinear, a proporção de Steiner é exatamente 3/2.^[33], a proporção que é a obtida por quatro pontos em um quadrado com uma árvore que utiliza 3 lados do quadrado e uma arvore de Steiner que conecta pelo centro do quadrado.^[33] Mais precisamente, para a distância L₁ o quadrado deveria ser rotacionado 45° a respeito dos eixos de coordenada, enquanto que para a distância L_∞ o quadrado deveria ser alinhado com o eixo.

• 
  Árvores de Steiner

• Problema do caixeiro-viajante

Referências

O Commons possui uma categoria com imagens e outros ficheiros sobre Problema da árvore de Steiner

• «GeoSteiner» (em inglês). Software para resolver problema da árvore de Steiner euclidiana e retilinear; código fonte disponível, gratuito para uso não comercial 
• «SCIP-Jack» (em inglês). Software para resolver o problema da árvore de Steiner em grafos e 14 variantes, por exemplo, problema da árvore de Steiner para coleta de prêmios; gratuito para uso não comercial 
• «Fortran subroutine» (em inglês). para encontrar o vértice de Steiner de um triângulo (isto é, Ponto de Fermat), suas distâncias dos vértices do triângulo e os pesos relativos dos vértices 
• «Phylomurka» (em inglês). Solucionador para o problema da árvore de Steiner em redes 
• Noormohammadpour, Mohammad; Raghavendra, Cauligi S.; Rao, Sriram; Kandula, Srikanth (2017), «Using Steiner Trees to Minimize Average Completion Times of Bulk Data Transfers», DCCast: Efficient Point to Multipoint Transfers Across Datacenters, USENIX Association, arXiv:1707.02096 
• «M. Hauptmann, M. Karpinski (2013): A Compendium on Steiner Tree Problems» (em inglês)