# Travelling Salesman Problem where a subset of the nodes must be visited in a particular order

I’m curious whether there is any work on the variant of the Travelling Salesman Problem where a subset of the nodes must be visited in a particular order. I haven’t found anything with searches or in survey articles, but that may just mean I haven’t found the right search terms or the right surveys.

If there are $n$ nodes in the graph, and a list $a_1, \dots, a_k$ of nodes that must be visited in that order, I can transform the problem to an instance of ATSP with $2k(n-k)+k$ nodes. The result is asymmetric even if the original edge-weights were symmetric, so we lose another factor of $2$ if we want to reduce it to a symmetric instance. I would be interested to know if there is a more efficient reduction.

Edited to add: On further reflection I think I can improve the reduction to $k(n-k)+k$ nodes.

• In the ATSP Path setting we considered such a generalization. See paper theoryofcomputing.org/articles/v003a010/index.html. I had forgotten but the paper also points to a result for the metric case (undirected graphs) where a 3-approximation is feasible. – Chandra Chekuri Nov 6 '16 at 4:00
• @ChandraChekuri Thanks! That link isn't working for me right now (server not responding) but I'll check it out when I can. – Robin Houston Nov 6 '16 at 12:49