Traveling Salesman Problem is NP-Complete

The validity of the material on this page is questionable. In particular: The predicate "NP-Complete" usually only applies to decision problems -- the optimization version is not of that kind. So even though it is NP and NP-Hard, it cannot be NP-Complete. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Questionable}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Problem Statement

There are two versions of the Traveling Salesman Problem.

The function or optimization version:

Given a complete weighted graph $G$ with positive integer weights find a Hamilton Cycle in $G$ with minimum weight.

The decision version:

Given a complete weighted graph $G$ with positive integer weights and a maximum weight $m$ decide if $G$ has a Hamilton Cycle with a total weight of at most $m$.

Theorem

Both versions of the Traveling Salesman Problem are NP-complete.

The Function Version of the Problem is Reducible to the Decision Version of the Problem

The size of the Traveling Salesman Problem can be measured by $n^2 ln \left({s}\right)$ where $n$ is the number of cities and $s$ is the maximum weight of any edge of the graph.

The following algorithm solves the function version of the Traveling Salesman problem by solving $O \left({ln \left({s}\right)}\right) + O \left({n^2}\right)$ instances of the decision problem.

Input: A weighted graph $G$

Output: The Minimum Hamilton Cycle in $G$

Auxiliary Functions: $f \left({G,m}\right) = 1$ if $G$ contains a Hamilton Cycle with weight at most $m$, and equals $0$ otherwise

Determining $m$

Set $Max$ initially to $s n$.

Set $min$ initially to $0$.

While $min + 1 \ne Max$

Set $cut$ at $\left\lfloor {\dfrac {min + Max} 2}\right\rfloor$.

Calculate $f \left({G, cut}\right)$.

if the value is $1$ replace $min$ with $cut$.

Otherwise replace $Max$ with $cut$.

At this point $min$ is the weight of the minimum path through $G$.

Call that number $m$.

Calculating the path

Pick a starting vertex as a focus vertex.

Call it $v$.

The solution path starts at $v$.

Until the solution path is a Hamilton Cycle:

Pick one of the edges going out of the focus vertex that has not been considered before in this algorithm.

Call that edge $\left({v, u}\right)$.

Change the weight of $\left({v,u}\right)$ with a larger number (such as $m$).

If $f \left({G, m}\right) = 1$ leave the edge at the higher weight.

Otherwise add $u$ to the end of the solution set, return the weight of the edge to the original weight, and change the focus vertex to $u$.

At this point the solution path is the minimal Hamilton Cycle in the original graph.

This polynomially reduces the function problem to the decision problem.

Likewise the decision problem can be reduced to the function problem by finding the minimal Hamilton Cycle in $G$, adding the weights of the included edges together and checking to see if that number is less then $m$.

Because they are both polynomially reducible to each other we can show that they are both NP and NP-hard by showing that one of them is.

The Traveling Salesman Problem is NP

Given a graph $G$, an upper bound $m$, and a possible solution in the form of a Hamilton path it is possible to verify or reject that solution with $n$ additions and a single numerical comparison.

This can be accomplished in polynomial time.

By NP Problem iff Solution Verifiable in Polynomial Time the decision version of the Traveling Salesman Problem is NP.

This implies both versions are NP.

$\Box$

The Traveling Salesman Problem is NP-hard

Directed Hamilton Cycle Problem is NP-complete.

By reducing that problem to the Traveling Salesman problem we can show that the Traveling Salesman Problem is NP-hard.

The reduction is fairly straightforward.

Let $G$ be a directed graph with $n$ vertices.

Construct a new weighted complete graph $G'$ with the same vertices where the weight of the edge $\left({v, u}\right)$ has:

weight $1$ if the edge $\left({v, u}\right)$ is in the original graph $G$

weight $ n + 1 $ otherwise.

$G$ has a Hamilton Cycle if there is a Hamilton Cycle in $G'$ with a total weight of $n$.

The Directed Hamilton Cycle problem reduces to the Traveling Salesman Problem, therefore the Traveling Salesman Problem is NP-hard.

$\Box$

Because the Traveling Salesman problem is both NP and NP-hard the Traveling Salesman Problem is NP-complete.

$\blacksquare$