Search code examples
algorithmgraph-theorynp-completenp-hard

Why is TSP NP-hard while the Hamiltonian path NP-complete?

Why aren't these 2 problems, namely TSP and Hamiltonian path problem, both NP-complete?

They seem identical.

Solution

  • For a problem X to be NP-complete, it has to satisfy:

    1. X is in NP, given a solution to X, the solution can be verified in polynomial time.
    2. X is in NP-hard, that is, every NP problem is reduceable to it in polynomial time (you can do this through a reduction from a known NP-hard problem (e.g. Hamiltonian Path)).

    There are two versions of the The Travelling Salesman Problem (TSP):

    1. The optimization version (probably the one you are looking at), namely, find the optimum solution to the TSP. This is not a decision problem, and hence cannot be in NP, but it is however in NP-hard which can be proven via a Hamiltonian Path reduction. Therefore this isn't an NP complete problem.
    2. The decision version - given an integer K is there a path through every vertex in the graph of length < K? This is a decision (yes/no) problem, and a solution can be verified in polynomial time (just traverse the path and see if it touches every vertex) and so it is in NP, but it is also in NP-hard (by an identical proof as above). Since it satisfies both requirements for NP-completeness, it is an NP-complete problem.