HC to TSP

TSP.md

Goal: show that TSP is NP-complete

• TSP is NP
• TSP is NP-Hard

TSP is NP

• Algorithm: given a tour, sum the weights, and see if it exceeds the bound
• The verifier runs in polynomial time

TSP is NP-Hard

• Every NP problem reduces to TSP in polynomial time

Every NP problem reduces to TSP in polynomial time

• Every NP problem reduces to HC in polynomial time: HC is NPC
• Every problem in HC reduces to TSP in polynomial time

Every problem in HC reduces to TSP in polynomial time

• Make HC problem a TSP problem, in polynomial time
• HC ⇔ TSP

Recall that the decision version of HC is : Given a graph G=(V,E), does there exist a simply cycle in G that traverses every vertex exactly once? Now proceed to observe that a simple cycle on n vertices has n edges. Now to reduce HC to TSP, employ the following algorithm. Take G=(V,E), set all edge weights equal to 1, and let k = |V|=n, that is, k equals the number of nodes in G. Any edge not originally in G then receives a weight of 2 (traditionally TSP is on a complete graph, so we need to add in these extra edges). Then pass this modified graph into TSP, asking if there exists a Tour on G with cost at most k. If the answer to TSP is YES, then HC is YES. Likewise if TSP is NO, then HC is NO.

Proof: We must show that the reduction takes polynomial time and that solutions for HC are in 1-1 correspondence with solutions to TSP using the reduction. Clearly, the reduction takes polynomial time, so we are left with the latter.

HC has a YES answer ⇒ TSP has a YES answer

Proof: If HC has a YES answer, then there exists a simple cycle C that visits every node exactly once, thus C has n edges. Since every edge has weight 1 in the corresponding TSP instance for the edges that are in the HC graph, there is a Tour of weight n. Since k=n, and given that there is a Tour of weight n, it follows that TSP has a YES answer.

HC has a NO answer ⇒ TSP has a NO answer

Proof: If HC has a NO answer, then there does not exist a simple cycle C in G that visits every vertex exactly once. Now suppose TSP has a YES answer. Then there is a tour that visits every vertex once with weight at most k. Since the Tour requires every node be traversed, there are n edges, and since k=n, every edge traversed must have weight 1, implying that these edges are in the HC graph. Then take this tour and traverse the same edges in the HC instance. This forms a Hamiltonian Cycle, a contradiction.

This concludes Part 2. Since we have shown that TSP is both in NP and NP-Hard, we have that TSP is NP-Complete, as required.