Localizando caminhos min-max vertic-disjoint com uma fonte comum em gráficos planares

10

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.(s,t1),,(s,tk)k2ksti

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 ;kt1==tk
  • 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 ;(s1,t1),,(sk,tk)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 ;k
    • aberto para fontes não coincidentes e constante .k
Sergey Pupyrev
fonte
4
Parece que existem muitos resultados relacionados. Você pode resumir resultados relacionados importantes na pergunta?
Tsuyoshi Ito
O gráfico de entrada G é ponderado (ou seja, cada aresta tem um comprimento inteiro positivo)? Eu estava assumindo que G não é ponderado, mas percebi que você provavelmente está misturando as duas configurações: (1) Se G é ponderado, então o caso de k = 2 é NP-completo essencialmente pelo Teorema 14 no artigo por Kobayashi e Sommer aos quais você se vinculou, que também é essencialmente o mesmo que o último parágrafo da Seção 2 de [HP02] citado na minha resposta. (2) Se G não é ponderado, não vejo por que o artigo de Kobayashi e Sommer implica a dureza NP no caso de k = 2 e fontes diferentes.
Tsuyoshi Ito
Nas minhas configurações, um gráfico não é ponderado, então você está certo: minha reivindicação sobre a dureza NP no caso de K = 2 e fontes diferentes (provavelmente) está errada.
Sergey Pupyrev 24/11/11
Atualizei a declaração do problema levando em consideração o comentário de Tsuyoshi Ito.
Sergey Pupyrev

Respostas:

6

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

Tsuyoshi Ito
fonte
kk
@SergeyPupyrev: Você escreveu que k é uma constante. (Você escreveu porque sabia o que significa, não sabia?) Pelo que aprendi com uma análise superficial de artigos relevantes, se k é uma constante ou não em problemas relacionados, parece fazer uma enorme diferença no status atual de a complexidade do problema.
Tsuyoshi Ito
kk
11
@SergeyPupyrev: Não consigo encontrar um documento que declare a complexidade no caso em que k é uma constante, mas isso significa apenas que não me é conhecido .
Tsuyoshi Ito