Adicione uma correspondência a um caminho hamiltoniano para reduzir a distância máxima entre pares de vértices

14

Qual é a complexidade do seguinte problema?

Entrada :

  • H umcaminho hamiltonianoemKn
  • um subconjunto de pares de vérticesR[n]2
  • um número inteiro positivo k

Consulta : existe um M correspondente que para cada ( v , u ) R , d G ( v , u ) k ? (onde G = ( [ n ] , M H ) )M(v,você)RdG(v,você)k
G=([n],MH)

Eu tenho tido uma discussão com um amigo sobre este problema. Meu amigo acha que o problema está no tempo polinomial. Eu acho que é NP-completo.

pfim
fonte
11
Você pode simplificar isso ainda mais, pelo menos em termos de apresentação. Você recebe , um caminho com n vértices e uma coleção R de pares desses vértices. Você deseja aumentar o caminho com uma correspondência para que a distância entre qualquer par em R seja no máximo k . knRRk
precisa
Acho que essa formulação pode ser confusa após a minha edição mais recente para remover alguma ambiguidade.
Pembro 04/04
1
Minha interpretação está correta, não é?
Sasho Nikolov
Fiz uma edição para tornar a declaração do problema mais rigorosa. Eu acho que isso pode ser mais simplificado, porque, como você pode simplesmente assumir que H é o caminho hamiltoniano 1-2-3-4-5 ...- n sem perda de generalidade. Então você só precisa . n
Kaveh

Respostas:

1

Esta resposta está incorreta .

Seu amigo está certo. Seu problema (conforme interpretado por Sasho) não impõe nenhuma restrição à cardinalidade do correspondente . Por conseguinte, escolher C ser uma correspondência entre os pares em R . Então, para qualquer número inteiro positivo k , a distância entre cada par em R é menor que k .CCRkRk

Seu problema torna-se interessante se você forçar caminhos para conter bordas tanto da correspondência eo caminho P .CP

Mohammad Al-Turkistany
fonte
O que você quer dizer com "correspondência entre os pares em "? R
Emil Jeřábek apoia Monica
@ EmilJeřábek Significa conectar os nós de cada par em por uma borda. Então C é apenas R com uma borda conectando todos os pares. Isto é equivalente a aumentar o caminho P com uma marcha perfeita sobre os pares de R . RCRPR
Mohammad Al-Turkistany 04/04
1
Isso não parece fazer muito sentido para mim. E se não for uma correspondência? Digamos, se R contém os pares ( 1 , 2 ) e ( 1 , 3 ) , como você escolhe C ? RR(1,2)(1,3)C
Emil Jeřábek apoia Monica
@ EmilJeřábek Sim. Seu ponto é válido. Vou editar minha resposta.
Mohammad Al-Turkistany 04/04
@pfim O caminho mais curto pode ser formado usando apenas arestas de ? C
Mohammad Al-Turkistany 04/04
0

UPDATE: a resposta abaixo não está correta, porque assumi erroneamente que o caminho hamiltoniano está em um gráfico arbitrário, não em . Deixo-o sem exclusão, talvez eu conserte ou dê algumas dicas para outra resposta.Kn

Eu acho que é NP-completo. Esta é uma ideia de redução muito informal / rápida da 3SAT

Para cada variável adicionar um "dispositivo variável" com:xi

  • três nós Xi,+Xi,Xi
  • duas arestas variáveis e ( X i , - X i )(Xi,+Xi)(Xi,Xi)

Inclua um nó de origem e conecte-o a todas as variáveis X i .SXi

Para cada cláusula adicione um nó C j e conecte-o às variáveis ​​correspondentes + X i ou - X i que formam a cláusula.CjCj+XiXi

A figura a seguir representa: (+x1x2x3)(x2x3x4)

insira a descrição da imagem aqui

O conjunto (nodos que devem ser ligadas) contém ( S , C 1 ) , ( S , C 2 ) , . . .R(S,C1),(S,C2),...

O caminho simples deve incluir todas as arestas "AZUIS", exceto as arestas variáveis ( X i , + X i ) e ( X i , - X i ) (na figura acima, as arestas azuis representam as arestas incluídas emP(Xi,+Xi)(Xi,Xi)P ).

Nesse ponto, a fórmula inicial é satisfatória se e somente se o caminho mais curto de para cada nó da cláusula C j não for maior que três. De facto para atingir uma cláusula de S em três passos que devem atravessar, pelo menos, uma variável X i : S X i± X iC j . Portanto, devemos atravessar uma das duas arestas: X i+ X i ou X i- X i ) e incluí-la em CSCjSXEuSXEu±XEuCjXEu+XEuXEu-XEu)C (porque, por construção, não faz parte de P ). Mas ambos não podem ser incluídos, porque compartilham um vértice.

Mas não temos certeza de que podemos construir um caminho simples que inclua todas as arestas azuis porque alguns nós têm mais de uma aresta azul incidente.P

Para corrigir isso, substituímos cada nó por várias arestas azuis incidentes, por uma árvore que contém apenas pares de arestas azuis incidentes que serão incluídas em e arestas que as separam e que devem ser incluídas em C para alcançar os nós da cláusula:PC

insira a descrição da imagem aqui

O gráfico original se torna:

insira a descrição da imagem aqui

Cada árvore deve ter a mesma profundidade (podemos escolher o máximo da profundidade necessária para todas as cláusulas / variáveis ​​/ S); e devemos aumentar o valor de acordo (o número de etapas para alcançar C j deKCjS

Podemos incluir em C todas as arestas necessárias (não azuis) necessárias para alcançar os nós da cláusula porque elas não compartilham nenhum vértice.

P

insira a descrição da imagem aqui

Marzio De Biasi
fonte
Tentar criar um caminho que contenha todas as bordas azuis me preocupa: alguns vértices têm mais de 2 bordas azuis incidentes nelas, portanto, não pode haver um caminho simples, incluindo todas as bordas azuis.
Mikhail Rudoy
Ok, obrigado ... Esqueci completamente o que é um caminho simples :-( ... agora ele deve ser corrigido.
Marzio De Biasi
Este post no math.SE sugere que o problema pode não estar completo. Poderia ser intratável, mas resolvidos em tempo quasipolynomial math.stackexchange.com/questions/2218929/...
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: você vê uma falha na versão atual da resposta?
Marzio De Biasi
Não, não vejo nenhuma falha óbvia.
Mohammad Al-Turkistany 06/04