4
$\begingroup$

Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted?
That is, each node in the topological graph should be visited once at least (instead of exactly).

Is it still NP-complete or reduced to a P problem?
How would this modification affect classical methods for solving the original TSP such as dynamic programming, mixed integer programming, meta-heuristics and maybe branch-and-cut/bound/price?

What I have tried:

I believe this variant might be easier to solve, but after a sketchy thought about the MIP model, I found it is hard to write the sub-tour elimination constraints.

I have checked TSP Where Vertices Can be Visited Multiple Times but it is asking for a working solution which could be a heuristic that does not guarantee the optimality and computational time. This is not what I want.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

No, it doesn't become easier. Metric TSP (the version where the distances obey the triangle inequality) is still NP-complete but, in this scenario, the shortest tour always visits every city exactly once. The triangle inequality guarantees that going directly to a new city is always faster than going there via somewhere you've already been.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Also, with arbitrary distance TSP you could replace each distance from A to B with the shortest path from A to B in polynomial time, so solving "Metric TSP" solves "TSP without single path constraint" completely. $\endgroup$
    – gnasher729
    Jun 17, 2017 at 16:46
  • $\begingroup$ @gnasher729 if "TSP without single path constraint" (A) can be reduced to "Metric TSP" (B), we can infer that B is harder than A only. e.g. "deciphering codes with the key" (A) can be reduced to "deciphering without the key" (B) by just forgetting the key, it is clear that B is harder than A and solving A is pretty easy. $\endgroup$
    – Mr. Ree
    Jul 23, 2017 at 1:02

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.