Skip to main content
MathOverflow

Return to Answer

added 4 characters in body
Source Link
user117147
user117147
  • 81
  • 2

The Hamiltonian-circuit problem (which is known to be NP-complete) is polynomially reducible to TSP: Given a graph $G$ on $n$ vertices construct an edge-weighted $K_n$ complete graph with edge weights 0 and 1, so that the weight-0 edges span a subgraph isomorphic to $G$. Now $G$ is Hamiltonian iff the minimal tour in $K_n$ has cost zero. Therefore there iscan be no poly-time algorithm for TSP unless P=NP.

The Hamiltonian-circuit problem (which is known to be NP-complete) is polynomially reducible to TSP: Given a graph $G$ on $n$ vertices construct an edge-weighted $K_n$ complete graph with edge weights 0 and 1, so that the weight-0 edges span a subgraph isomorphic to $G$. Now $G$ is Hamiltonian iff the minimal tour in $K_n$ has cost zero. Therefore there is no poly-time algorithm for TSP unless P=NP.

The Hamiltonian-circuit problem (which is known to be NP-complete) is polynomially reducible to TSP: Given a graph $G$ on $n$ vertices construct an edge-weighted $K_n$ complete graph with edge weights 0 and 1, so that the weight-0 edges span a subgraph isomorphic to $G$. Now $G$ is Hamiltonian iff the minimal tour in $K_n$ has cost zero. Therefore there can be no poly-time algorithm for TSP unless P=NP.

Source Link
user117147
user117147
  • 81
  • 2

The Hamiltonian-circuit problem (which is known to be NP-complete) is polynomially reducible to TSP: Given a graph $G$ on $n$ vertices construct an edge-weighted $K_n$ complete graph with edge weights 0 and 1, so that the weight-0 edges span a subgraph isomorphic to $G$. Now $G$ is Hamiltonian iff the minimal tour in $K_n$ has cost zero. Therefore there is no poly-time algorithm for TSP unless P=NP.