Chemin le plus court du nœud A vers B en passant par tous les autres nœuds (NP-Hard?)

Question

Mon problème: Trouver le chemin le plus court entre le nœud A et le nœud B qui traverse tous les autres nœuds du graphe direct non pondéré. Je sais qu'il existe un tel chemin. Je crois que c'est NP-Hard, mais je ne peux pas l'expliquer. Mon prof aime que l'algorithme fonctionne sur un temps d'exécution de O(|V| + |E|), où V est l'ensemble des noeuds et E l'ensemble des arêtes.

Il semble qu'il soit similaire à this problem, mais les propriétés du graphique sont différentes, cela fait-il une différence?

Answer 1

Oui c'est NP-difficile. Si votre solveur a couru dans P, alors en l'exécutant sur chaque paire de points, vous aurez un solveur P-time pour Hamiltonian Path. Le answer you linked donne une preuve plus rigoureuse.