Since planar TSP with n nodes is NP-hard, we cannot simply find an optimal solution with n-1 nodes and then insert the remaining node at one of the solution's edges to find the optimal solution of the original TSP problem. So, is there a planar graph with an optimal solution, such that when we add a certain extra node, the new graph's optimal solution has none of the edges of the previous optimal solution?

  • $\begingroup$ When you say planar TSP, do you mean Euclidean TSP? I.e. a set of points in $\mathbb{R}^2$ with Euclidean distances? $\endgroup$
    – G. Bach
    Nov 9 '15 at 20:57
  • $\begingroup$ yesm that's what I mean. $\endgroup$ Nov 17 '15 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.