Question

Optimization versus search.Recall the traveling salesman problem:

TSP

Input: A matrix of distances; a budget b

Output: A tour which passes through all the cities and has $\mathbf{\text{length}}\mathbf{\le }\mathit{b}$, if such a tour exists.

The optimization version of this problem asks directly for the shortest tour.

TSP-OPT

Input:A matrix of distances

Output:The shortest tour which passes through all the cities.

Show that if TSP can be solved in polynomial time, then so can TSP-OPT.

Short answer

The TSP is solved in the polynomial time by the binary search, then by the binary search routine TSP-OPT is also solved in polynomial time.

Step-by-step solution

Explain Traveling Salesman Problem

Travelling salesman problem deals with the set of cities and the distance between the cities. The aim of the problem is to find the shortest route that leads to visit every city exactly once. A tour is a walk around the city that does not use any route or edge more than once and ends with the city that tour has begun.

Show that if TSP can be solved in polynomial time, then so can TSP-OPT.

In order to solve TSP-OPT in polynomial time, the TSP has to be called to polynomial number of calls with varying input using binary search. Consider the graph G with the cities as vertices and the routes as edges. Consider Tbe the sum of all the edge weights and minimum tour is at most T.

Start the binary search on TSP with$b=\frac{T}{2}$, If found then the min tour must be between 0 and $\frac{T}{2}$. If the answer is not found, then the value of the min tour must be between T and $\frac{T}{2}$. Continue the binary search until the resolution of the min-edge length is reached in the graph. The complexity of the binary search must be polynomial in the input argument.

Consider L be the largest edge weight and to replace all the edge weights with L , It takes at most $\left|E\right|\log L$bits to represent T. The former representation is still polynomial in the input size.

Therefore, only a polynomial number of calls to TSP using binary search solves the TSP-OPT in polynomial time.