Dado um gráfico planar não ponderado e uma coleção de pares de vértices ( k ≥ 2 é uma constante), encontre k caminhos verticais-disjuntos (exceto a origem) de s a t é tal que o comprimento do caminho mais longo é minimizado.
Pergunta: Existe um algoritmo de tempo polinomial para o problema?
Alguns resultados relacionados:
- se não for corrigido, o problema é NP-difícil, mesmo que t 1 = ⋯ = t k ;
- se o gráfico de entrada for ponderado e as fontes dos caminhos não coincidirem, ou seja, os caminhos são o problema é NP-difícil, mesmo para k = 2 ;
um problema com objetivo diferente, ou seja, minimizar a soma dos comprimentos do caminho, é
- solucionável com o algoritmo de fluxo de custo mínimo para fontes coincidentes;
- NP-difícil para fontes não coincidentes e geral ;
- aberto para fontes não coincidentes e constante .
ds.algorithms
graph-algorithms
Sergey Pupyrev
fonte
fonte
Respostas:
Não foi exatamente isso que você pediu, mas o problema é NP-completo se k não for uma constante, mas fizer parte da entrada.
Isto resulta da prova do Teorema 1 em van der Holst e de Pina [HP02], que diz: dado um gráfico planar L , vértices distintos s e t em L e números inteiros positivos k e b , é NP-completo para decidir se existem k caminhos par-vértices-disjuntos internamente emparelhados entre s e t cada um de comprimento no máximo b .
Observe que o problema na declaração do Teorema 1 é diferente do seu em dois aspectos. Uma diferença é, como mencionei, que k é dado como parte da entrada. A outra é que o problema no [HP02] é sobre caminhos com pontos de extremidade comuns, em vez de caminhos com uma fonte comum e sumidouros diferentes. Não sei como consertar a primeira diferença; a diferença é tão grande que é provável que precisemos de uma prova completamente diferente para corrigir k . Mas sei pelo menos como consertar a segunda diferença.
A prova do Teorema 1 em [HP02] fornece uma redução em relação ao 3SAT. Essa redução possui a seguinte propriedade: na instância ( G , s , t , k , b ) construída pela redução, o grau do vértice t é sempre igual a k . Vamos t 1 , ..., t k ser os k vizinhos de t . Então, em vez de perguntar se existem k caminhos par-internos separados por vértices k em pares entre s e t cada um de comprimento no máximo bPodemos igualmente perguntar se existem pairwise vértice-disjuntos-excepto-fonte caminhos P 1 , ..., P k tal que cada P i é um caminho entre s e t i de comprimento, no máximo, b -1.
H. van der Holst e JC de Pina. Caminhos disjuntos com limite de comprimento em gráficos planares. Matemática Aplicada Discreta , 120 (1–3): 251–261, agosto de 2002. http://dx.doi.org/10.1016/S0166-218X%2801%2900294-3
fonte