The Traveling Salesman Problem (TSP) is defined as follows:given a complete, weighted, undirected graph on n vertices(i.e., there is an edge between every pair of vertices) and anumber k > 0, does there exist a cycle going throughevery vertex exactly once with total weight at most k?(The weight of a cycle is the sum of the weights of the edgesforming the cycle.)
The Hamiltonian Cycle (HC) problem is defined as follows: givenan undirected graph, does there exist a cycle that goes throughevery vertex exactly once?
Show that HC is polynomially-reducible to TSP, i.e., HC ≤ P TSP.In other words, assume that we
OR
OR