<p>This is a special case of the precedence-constrained TSP which has been studied quite a lot. For instance, there are a polyhedral analysis by <a href="http://link.springer.com/article/10.1007/BF01585767" rel="nofollow noreferrer">Balas, Fischetti and Pulleyblank</a>, and a branch-and-cut algorithm by <a href="http://link.springer.com/article/10.1023/A:1008779125567" rel="nofollow noreferrer">Ascheuer, Jünger and Reinelt</a>.</p>

CC BY-SA 3.0
2016-11-06T13:01:49.683Z
Great, thanks! It looks indeed as though “precedence-constrained TSP” is a key search term I was missing.
Robin Houston
CC BY-SA 3.0
2016-11-05T19:35:10.507Z
2016-11-05T19:35:10.507Z
Thomas Kalinowski
<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2016-11-06T04:00:46.683Z
In the ATSP Path setting we considered such a generalization. See paper http://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
CC BY-SA 3.0
2016-11-06T12:49:29.053Z
@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
<graph-algorithms><tsp>
Travelling Salesman Problem where a subset of the nodes must be visited in a particular order
Robin Houston
# Travelling Salesman Problem where a subset of the nodes must be visited in a particular order

(Asked by: username_0 on 2016-11-05)

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.

**Tags:** graph-algorithms, tsp

> **Comments:**
> **username_1**: In the ATSP Path setting we considered such a generalization. See paper http://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.  
> **username_0**: @ChandraChekuri Thanks! That link isn't working for me right now (server not responding) but I'll check it out when I can.  

---

## 1 answers

### Answer by username_2 on 2016-11-05. Score: 4 | Accepted answer

This is a special case of the precedence-constrained TSP which has been studied quite a lot. For instance, there are a polyhedral analysis by [Balas, Fischetti and Pulleyblank](http://link.springer.com/article/10.1007/BF01585767), and a branch-and-cut algorithm by [Ascheuer, Jünger and Reinelt](http://link.springer.com/article/10.1023/A:1008779125567).

> **Comments:**
> **username_0**: Great, thanks! It looks indeed as though “precedence-constrained TSP” is a key search term I was missing.  

---

