0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ I initially misunderstood your question. Are you asking if there are practical applications of the problem described in option 1? Also, not sure why you call it "unit edge costs", since the edge costs can be 1 or 2, not 1 or $\infty$. Cost 2 is not unitary. $\endgroup$
    – Vincenzo
    Jan 9, 2019 at 15:14
  • $\begingroup$ @Vincenzo "Cost 2 is not unitary" it's not, I oversimplified. $\endgroup$
    – Abhijit Sarkar
    Jan 16, 2019 at 2:01

2 Answers 2

Reset to default
2
$\begingroup$

Statement 1 is false (assuming P $\neq$ NP) because any instance $G$ of the NP-complete Hamiltonian Cycle problem can be reduced to an instance of the TSP in which every edge cost is either 1 or 2.

Why? Define a TSP instance on a complete graph $K_n$, with edge cost 1 whenever the corresponding edge is also in the original graph $G$, and edge cost 2 otherwise. Now a TSP tour of cost $\le n$ exists in the complete graph if and only if $G$ has an Hamiltonian cycle.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Any Hamiltonian Cycle problem on graph G can be reduced to TSP on graph G' in polytime, or equivalently, using cost 0 for edges present in the G and 1 for those are aren't. It's not specific to the problem at hand. $\endgroup$
    – Abhijit Sarkar
    Jan 8, 2019 at 18:52
  • $\begingroup$ @AbhijitSarkar Yes, but this answer proves that the special case the question asks about is NP-hard. $\endgroup$
    – Draconis
    Jan 16, 2019 at 2:07
  • $\begingroup$ @Draconis My question wasn't about the NP-Hard problem, it was about the TSP special instance with edge cost is either 1 or 2. See my answer. $\endgroup$
    – Abhijit Sarkar
    Jan 16, 2019 at 2:51
  • $\begingroup$ @AbhijitSarkar Yes, what we're saying is that that special case is also NP-hard. Thus, 1 is false. $\endgroup$
    – Draconis
    Jan 16, 2019 at 2:52
  • $\begingroup$ @Draconis I think the papers I referred to in my answer provide more insight than a blanket statement "no NP-Hard instance has a polytime optimal solution". Sure, that's true, but more diligence is appreciated in researching the specific subproblem, which is exactly what the papers do. $\endgroup$
    – Abhijit Sarkar
    Jan 16, 2019 at 2:59
-1
$\begingroup$

OP here.

Papadimitriou and Yannakakis have shown that it is possible to approximate the TSP problem 1 in polynomial time within accuracy $ \frac{7}{6} $. This guarantee has been further improved by Bläser and Shankar Ram to $ \frac{65}{56} $. However, no matter how good those results are, they are still approximations, and not an optimal solution. Thus, option 1 is incorrect.

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 '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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.