Show that the decision problem related to Traveling Salesperson problem is in NP

Question

Show that the decision problem related to Traveling Salesperson problem is in NP by providing pseudocode for an algorithm which verifies a legal salesperson circuit in the graph. Inputs: G = , where W represents the weights of the edges. Also, a circuit C consisting of a sequence of edges in E. Finally, a maximum distance m which the salesperson can travel. Your algorithm should return True if the sequence C has length less than or equal to m and it connects all vertices in the graph, returning to the starting position, without missing or repeating a vertex on the way. Return False otherwise.

Explanation / Answer

Assuming the existence of an efficient algorithm A for the Decision-TSP, you can take any instance G=(V,E,W) for the Hamiltonian cycle problem and convert it into an instance G'=(V,E'=V×V,W),C=0 of Decision-TSP as above E->(e)=1e->E such that

if there is a Hamiltonian cycle in G then A will return "yes" on input (G',C)
if there is no Hamiltonian cycle in G then the minimum Hamiltonian cycle in G' has cost at least 1, and thus A will return "no" on input (G',C)

Therefore, A can be used to solve the Hamiltonian cycle problem, efficiently since for any G, G' can be computed efficiently and running A on (G',C) is efficient as well.

First, we have to prove that TSP belongs to NP . If we want to check a tour for credibility , we check that the tour contains each vertex once. Then we sum the total cost of the edges and finally we check if the cost is m i nim u m . This can be com p leted in polynomial time thus TSP belongs to NP. Secondly we prove that TSP is NP-hard. One way to prove this is to show that Ham iltonian cycle TSP. Assum e G = ( V, E,W ) to be an instance of Ham iltonian cycle. An instance of TSP is then constructed.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.