complexity-theorynpnp-completenp-hard

Is Shortest Hamiltonian path NP-hard?

Hamiltonian Path is a path that connects all nodes without repeat and it is an NP-complete problem.

  1. Is the Shortest Hamiltonian Path (SHP) NP-hard?

  2. What is the difference between travelling salesman problem with SHP?

Solution

  • I assume the SHP problem is the Hamiltonian problem on the edge weighted graph. It is NP-hard because it is at least as hard as the Hamiltonian problem. Assume you have an algorithm to solve the SHP problem, then you apply the algorithm on a weighted graph with all edge weights are 1, it will solve the Hamiltonian problem with the same time complexity.

    TSP requires to return to the original vertex and you can visit each vertex more one once. SHP asks for the path which visits every vertex exactly once.