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

Qual é a complexidade do seguinte problema?

Entrada :

• $H$ umcaminho hamiltonianoem$K_n$
• um subconjunto de pares de vértices$R \subseteq [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,u) \in R$$d_G(v,u) \leq k$
$G = ([n], M\cup H)$

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.

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 .$C$$C$$R$$k$$R$$k$

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

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.$K_n$

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:$x_i$

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

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

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.$C_j$$C_j$$+X_i$$-X_i$

A figura a seguir representa: $(+x_1 \lor -x_2 \lor -x_3) \land (-x_2 \lor x_3 \lor x_4)$

O conjunto (nodos que devem ser ligadas) contém ( S , C 1 ) , ( S , C 2 ) , . . $R$$(S, C_1), (S,C_2), ...$

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 em$P$$(X_i, +X_i)$$(X_i, -X_i)$$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 i → C j . Portanto, devemos atravessar uma das duas arestas: X i → + X i ou X i → - X i ) e incluí-la em $S$$C_j$$S$$X_i$$S \to X_i \to \pm X_i \to C_j$$X_i \to +X_i$$X_i \to -X_i)$$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:$P$$C$

O gráfico original se torna:

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 de$K$$C_j$$S$

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$