O problema de trilha mais longa é mais fácil do que o problema de trilha mais longa?

O problema do caminho mais longo é NP-hard. A prova (típica?) Baseia-se na redução do problema do caminho hamiltoniano (que é NP-completo). Observe que aqui o caminho é considerado simples (nó). Ou seja, nenhum vértice pode ocorrer mais de uma vez no caminho. Obviamente, também é simples de borda (nenhuma borda ocorrerá mais de uma vez no caminho).

E se abandonarmos o requisito de encontrar um caminho simples (nó) e continuarmos a encontrar um caminho simples (borda). À primeira vista, uma vez que encontrar uma trilha euleriana é muito mais fácil do que encontrar um caminho hamiltoniano, pode-se ter alguma esperança de que encontrar o caminho mais longo seja mais fácil do que encontrar o caminho mais longo. No entanto, não consigo encontrar nenhuma referência que comprove isso, muito menos uma que forneça um algoritmo.

Observe que estou ciente do argumento aqui: /programming/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph No entanto, o argumento parece falho em sua forma atual, pois mostra basicamente que você pode resolver o caso simples de borda resolvendo o caso simples de nó em um gráfico diferente (portanto, a redução é inversa). Não está claro que a redução possa ser facilmente alterada para funcionar da outra maneira. (Ainda assim, mostra que pelo menos o problema de trilhas mais longas não é mais difícil do que o problema de trilhas mais longas.)

Existem resultados conhecidos para encontrar trilhas mais longas (caminhos simples)? Complexidade (classe)? Algoritmo (eficiente)?

graph-theory graph-algorithms hamiltonian-paths Jaspe
fonte

Este não é exatamente o mesmo problema, mas dê uma olhada no problema de Extensão Euileriana Mínima, que é bastante semelhante.

Talvez eu não tenha entendido bem a pergunta, mas o caminho hamiltoniano é NP-completo, mesmo em gráficos cúbicos, uma vez que toda travessia de um nó requer duas arestas, não há como reutilizar um nó duas vezes, mesmo se relaxarmos a condição do nó simples caminhos para caminhos simples; então o problema do caminho hamiltoniano permanece NP-completo.

Marzio De Biasi

@ Bangye: ok, mas em gráficos cúbicos se um nó for atravessado uma vez, então duas arestas devem ser usadas ... e o nó não poderá ser atravessado novamente (porque existe apenas uma aresta não-atravessada). Assim, em grafos cúbicos os nós podem não ser "repetido" (exceto para o último fio da trilha que pode ser incidente a um nó já percorrido)

Marzio De Biasi

Aqui está a referência: AA Bertossi, O problema do caminho hamiltoniano da borda é NP-completo, Information Processing Letters, 13 (1981) 157-159.

Lamine

@Lamine: Obrigado pelo esclarecimento. Eu não acho que você tenha que excluir seus comentários, porque seria muito natural ter uma idéia semelhante primeiro e ver que ela não funciona é realmente útil.

Yota Otachi

Respostas:

Pelos comentários acima: o problema do ciclo hamiltoniano permanece NP-completo, mesmo em gráficos de grade com grau máximo 3 [1], mas nesses gráficos toda travessia de um nó requer duas arestas e no máximo uma aresta permanece sem uso, portanto, um nó não pode ser percorrido duas vezes por um caminho euleriano.

Então, aparentemente, há uma redução imediata do problema do ciclo hamiltoniano para o seu problema: dado um gráfico de grade com grau máximo 3 , basta pedir uma trilha de comprimento . $G = (V,E)$ $|V|$

$u$ $V' = V \cup \{u',u''\}$ $E = E \cup \{(u,u'), (u,u'')\}$ $|V'| = |V|+2$ $u',u''$

[1] Christos H Papadimitriou, Umesh V Vazirani, Sobre dois problemas geométricos relacionados ao problema do vendedor ambulante, Journal of Algorithms, Volume 5, Edição 5, Edição 2, Junho de 1984, Páginas 231-246, ISSN 0196-6774

Marzio De Biasi
fonte

Estou tendo um pouco de dificuldade para casar com isso, assim como com outros comentários, com a facilidade conhecida de encontrar uma trilha euleriana. Ou é o ponto crucial que (aderindo ao seu exemplo) decidindo se existe ou não uma trilha "euleriana" de comprimentoé mais fácil do que decidir se existe ou não uma trilha de comprimento? Isso certamente seria uma surpresa para mim, mas definitivamente interessante.

| E |

$|E|$

| V |

$|V|$

Jasper

Nos gráficos cúbicos, você tem certeza de que não há uma trilha de comprimentode fato, todas as arestas têm um grau ímpar 3 ( complexidade ). Portanto, os problemas de encontrar uma trilha de comprimento(com o truque adicional ) é mais difícil (NPC); informalmente: para cada nó, existem três pares de arestas que podem ser usadas para construir a trilha, e você não conhece os "efeitos" de uma escolha até construir o restante da trilha. Em um gráfico normal, o caminho euleriano é fácil de calcular, pois a cada passo você pode ter certeza de que pode "retornar" ao nó inicial (consulte o algoritmo de Fleury).

| E |

$|E|$

O (1)

$O(1)$

| V |

$|V|$

u^{'}, u^{″}

$u',u''$

Marzio De Biasi