Como provar a integridade NP do caminho mais longo entre dois vértices com base no problema Hamilton NP-Hard

Question

Eu tenho esta pergunta:Eu tenho um gráfico não direcionado G(V, E) (onde V = conjunto de vértices, E = conjunto de arestas).Considere o caminho máximo entre dois vértices s e t:

LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t}

Um caminho simples é um caminho sem nenhum vértice repetido, ou seja,cada vértice pode ser visitado apenas uma vez.O comprimento do caminho é dado pelas arestas que o compõem.

Então, como posso mostrar que LPATH é um problema NP-Completo usando o problema do caminho de Hamilton como um problema NP-Difícil como referência?

Answer 1

Bem-vindo ao site!Deixar $G = (V,E)$ seja um gráfico não direcionado.Se $G$ é hamiltoniano, então existe um ciclo simples $C$ em $G$ contendo cada vértice, ou seja,o comprimento do $C$ é $|V|$.Observe que se você excluir qualquer aresta $vw$ de $C$, você acaba com um caminho de comprimento $ | V | - 1 $ entre $v$ e $w$.Por outro lado, se você encontrar um caminho simples $P$ de comprimento $|V| - 1$ entre dois vértices $v, w$ conectado por uma aresta, você pode adicionar a aresta $vw$ para $P$ para obter um ciclo hamiltoniano (como $P$ não pode conter $vw$ por ser um caminho simples).Observe também que a escolha de $v$ e $w$ é arbitrário, desde que estejam conectados por uma aresta.

Assim podemos obter a seguinte redução:A partir de algum gráfico $G = (V,E)$, escolha alguma vantagem $vw \em E$ e exclua-o para obter um novo gráfico $G' = (V, E \setminus \{vw\})$.Usando as observações que fizemos, segue-se que $G'$ tem um caminho $P$ entre $v$ e $w$ de comprimento $|V| - 1$ se e somente se adicionar $vw$ para $P$ produz um ciclo hamiltoniano no gráfico original $G$.Como $G'$ pode ser calculado a partir $G$ em tempo polinomial, temos uma redução polinomial $\mathrm{Ciclo Hamiltoniano} \leq_\mathsf{P} \mathrm{Caminho Longo}$, mostrando assim que seu problema é $\matemática{NP}$-difícil (porque $\mathrm{Ciclo Hamiltoniano}$ é $\matemática{NP}$-difícil já).

Para mostrar isso $\mathrm{Caminho longo}$ é em $\matemática{NP}$ notamos que um caminho em um gráfico pode ser codificado eficientemente como uma lista de suas arestas e verificar se uma string realmente codifica um caminho no gráfico e então contar o número de arestas para determinar se é longo o suficiente pode ser feito em tempo polinomial .

Daí descobrimos que $\mathrm{Caminho longo}$ é $\matemática{NP}$-completo.