Travelling Salesman and Planar Travel - Generalized TSP Our beloved Travelling Salesman just bought the Manual of the Planes and wants to make some use of it. He is not a great adventurer though, so he will restrain his travels in the Parallel and Fundamental Planes, which are tightly coupled with the Material Plane (and try not to spend so much time in the Quasi-elemental Plane of Minerals and all the gold that lies there!). Let's say therefore that we have M-1 Parallel Planes and our salesman can visit each city in any of them. Travel from Material Neverwinter to Astral Luskan is of course different than travel from Material Neverwinter to Material Luskan and not always in a trivial manner (might cost more, might cost less). To make matters worse, the Salesman can visit each city in only one Plane and cannot therefore benefit from a portal connecting Shadow Waterdeep with Faerie Baldur's Gate if he initially arrived in Material Waterdeep (assume Dimensional Anchors covering the cities). So the Salesman has to complete his path using these new restrictions.

A 4th Level Wizard exclaimed instantly that this Plane Travelling Salesman has a problem that is not easier than those of his normal colleagues (just assume that the travel between two cities costs the same regardless of the Planes used and you have a classic TSP). The question is: How can he convert the problem into another that has already been researched by the scholars?



Less nerdy description:

Replace each of the N nodes in the original TSP with M subnodes. Distances are given for every pair of subnodes between different nodes. For each node, a single subnode must be used in the solution. Give an algorithm for the new problem.



Edit:

It turns out that it is indeed a well-researched problem so I am adding all the aliases I found for it.


Generalized TSP
Group TSP
TSP with Neighbourhoods
Set TSP
One-of-a-Set TSP
Multiple Choice TSP
Covering Salesman Problem
If the tour is required to visit one node in each group, then the problem is called Group-TSP, or TSP-with-neighborhoods. There's a ton of work on this in the plane (just google it), and in general it's as hard as HITTING SET (the case in which your metric is all 1s). There's a paper by Safra and Schwartz that shows that Geometric group TSP (in the plane) is hard to any constant factor.