Question

Show that the reduction of the Traveling Salesperson (Undirected) Decision Problem to the Traveling Salesperson Decision Problem can be done in poly. nomial time.

Short answer

The reduction of the Traveling Salesperson (Undirected) Decision Problem to the Traveling Salesperson Decision Problem can be done in polynomial time, specifically in \( O(n) \) where \( n \) is the number of edges in the original graph. This is due to each undirected edge in the UTSP being represented as two directed edges in the TSP.

Step-by-step solution

Understand the problem

In the UTSP, assume all edges are bidirectional with the same cost. This means the cost of traveling from City A to City B is equal to the cost of traveling from City B to City A. In contrast, in the TSP, the edges have directions and their costs may vary.

Create a new directed graph

To illustrate the reduction of UTSP to TSP, consider each undirected edge in the UTSP as two oppositely directed edges in the TSP. The cost assigned to these directed edges is the same as the undirected edge cost in the UTSP. Consequently, each undirected edge from the UTSP corresponds to two directed edges in the TSP.

Time complexity

The time complexity of such a transformation is \( O(n) \) where \( n \) is the number of edges in the original UTSP graph. This is because for each edge in the original graph, you only perform a constant amount of work: creating two new edges and assigning them a weight. Therefore, it's safe to say the reduction of UTSP to TSP can be done in polynomial time.

Conclusion

Since the directed TSP results from applying polynomial-time operations to the undirected TSP, it is correct to say that the reduction of the undirected problem to the directed one can be done in polynomial time.