Given a TSP instance $T$, decide whether changing the city coordinates by adding a vector of coordinates $v$ will change the optimal TSP objective by atleast $x$. The city coordinates are integers.

The problem is in PSPACE but even the verification problem seems to be NP-hard. Is that true?

If the verification problem is NP-hard, what exact complexity class does this problem belong to?

  • $\begingroup$ What do you mean by "adding a vector $v$?" $\endgroup$ – templatetypedef Jul 14 '12 at 0:16
  • $\begingroup$ By that I mean, we have the original vector $c$ of coordinates for the cities and we modify the coordinates by adding vector $v$ to $c$ where $v$ is also a vector of coordinates. $\endgroup$ – dpll Jul 14 '12 at 0:18
  • 2
    $\begingroup$ I expect that this is a tough question. Even the decision version of the usual Euclidean TSP (the traveling salesman problem where each city is a point on the plane and the distance between two cities is given as the Euclidean distance between the points, and your task is to decide whether there is a route whose length is at most a given threshold K) is not known to belong to NP for a reason which has nothing to do with the difficulty of TSP (Garey, Graham, and Johnson 1976 and Sum of Square Roots). $\endgroup$ – Tsuyoshi Ito Jul 14 '12 at 22:59

I'm assuming that you're thinking of the Euclidean traveling salesman problem, where $c$ and $v$ are vectors in $\mathbb{Z}^{2n}$, with two coordinates for each city. Let $minTSP(c)$ denote the length of the minimum traveling salesman tour for the cities with coordinates $c$. Then your problem asks whether $$ minTSP(c + v) \ge min TSP(c) + x. $$ But then the special case $c=0$ is equivalent to asking whether $minTSP(v) \ge x$, which is coNP-hard.

  • $\begingroup$ I don't understand your definition of minTSP(c). Waht is a tour "for cities with coordinates c"? There's just one city at c, isn't it? $\endgroup$ – HdM Jul 15 '12 at 15:05
  • $\begingroup$ No, there are $n$ cities, each represented by two coordinates, so there are $2n$ coordinates altogether. $\endgroup$ – JeffE Jul 15 '12 at 15:54

Your Answer

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

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