I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:
Which of the following statements is true?
- Consider a TSP instance in which every edge cost is either 1 or 2. Then an optimal tour can be computed in polynomial time.
- Consider a TSP instance in which every edge cost is negative. The dynamic programming algorithm covered in the video lectures might not correctly compute the optimal (i.e., minimum sum of edge lengths) tour of this instance.
- Consider a TSP instance in which every edge cost is negative. Deleting a vertex and all of its incident edges cannot increase the cost of the optimal (i.e., minimum sum of edge lengths) tour.
- Consider a TSP instance in which every edge cost is the Euclidean distance between two points in the place (just like in Programming Assignment #5). Deleting a vertex and all of its incident edges cannot increase the cost of the optimal (i.e., minimum sum of edge lengths) tour.
I argue as follows:
The DP algorithm doesn't make any assumptions on the edge costs, so option 2 is incorrect.
If all edge weights are negative, then deleting a vertex and all of its incident edges can certainly increase the minimum sum because in effect, that edge weight is now added to the previous minimum. Thus, option 3 is incorrect.
Take the optimal tour in the original instance. Now, instead of visiting the deleted vertex v, skip straight from v's predecessor to its successor on the tour. Because Euclidean distance satisfies the "Triangle Inequality", this shortcut only decreases the overall distance traveled. The best tour can of course only be better. Thus, option 4 is correct.
However, I'm not able to find any significance for TSP problems with unit edge costs. Is option 1 merely a trick, or is there more to it?