<p>As TSP is an optimization problem, there are not many variants of it (that I know of) that add hard constraints to the formulation. But if I have understood correctly, your problem is a special case of (a variant of) the Prize-Collecting Travelling Salesman Problem (PCTSP), which seems to be introduced in [1] <em>(NB: Technical report, written on typewriter. Hard to read)</em>:</p>
<p>Given a graph <span class="math-container">$G$</span> and a <em>prize</em> <span class="math-container">$w_v$</span> and a <em>penalty</em> <span class="math-container">$p_v$</span> for each vertex <span class="math-container">$v \in G$</span>, you are asked to construct a tour that minimizes the cost of travelling, plus the penalty for every vertex you do <em>not</em> visit. In addition, you have the constraint that the combined prize for every vertex you <em>do</em> visit must be higher than some prescribed sum <span class="math-container">$W$</span>.</p>
<p>If you are allowed to put negative values on your prizes, your problem can be formulated as a PCTSP this way:</p>
<ul>
<li>Let <span class="math-container">$p_v = 0$</span> for every <span class="math-container">$v\in V$</span></li>
<li>Let <span class="math-container">$w_a = n$</span> for every <span class="math-container">$a\in A$</span></li>
<li>Let <span class="math-container">$w_b = -1$</span> for every <span class="math-container">$b\in B$</span></li>
<li>Let <span class="math-container">$W = n\cdot |A| - k$</span></li>
</ul>
<p>It's worth it to add that having shorter routes often will lead to cheaper tours anyway. For example, if <span class="math-container">$G$</span> is metric, then you can just solve TSP on <span class="math-container">$G[A]$</span>, as visiting any vertices in <span class="math-container">$B$</span> will be considered a detour.</p>
<p>[1] <em>Balas, Egon</em>, <a href="http://dx.doi.org/10.1002/net.3230190602" rel="nofollow noreferrer"><strong>The prize collecting traveling salesman problem</strong></a>, Networks 19, No. 6, 621-636 (1989). <a href="https://zbmath.org/?q=an:0676.90089" rel="nofollow noreferrer">ZBL0676.90089</a>.</p>

CC BY-SA 4.0
2021-05-20T06:45:05.293Z
2021-05-20T06:45:05.293Z
Highheath
<p>I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for.
The story/idea is we have <em>ally</em> locations and <em>enemy</em> locations. We want to visit all allies while encountering few enemies. I thought of this when reading some papers in combinatorial optimization, but this is not my area of expertise. So, I don't know if I am searching the correct words.</p>
<p>The graph theoretic formulation is that we have an edge weighted graph <span class="math-container">$G = (V,E)$</span> which is bicolored so <span class="math-container">$V = A \cup B$</span> (note the coloring need not be proper, i.e. <span class="math-container">$G$</span> doesn't have to be bipartite). We are given an integer <span class="math-container">$k$</span> and want to find a minimum weight cycle (or alternatively path) which contains all vertices in <span class="math-container">$A$</span> and at most <span class="math-container">$k$</span> vertices in <span class="math-container">$B$</span>.</p>
<p>Has this problem been studied somewhere? Does it have a name or fit inside a known generalized TSP? Or maybe there is some reduction to known version of TSP?</p>
<p>When <span class="math-container">$k=0$</span> we can delete vertices in <span class="math-container">$B$</span> along with all edges incident to them and we have the usual TSP.</p>

<reference-request><graph-theory><graph-algorithms><co.combinatorics><optimization>
TSP with "enemy" nodes
John Machacek
# TSP with "enemy" nodes

(Asked by: username_0 on 2021-05-18)

I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for.
The story/idea is we have *ally* locations and *enemy* locations. We want to visit all allies while encountering few enemies. I thought of this when reading some papers in combinatorial optimization, but this is not my area of expertise. So, I don't know if I am searching the correct words.

The graph theoretic formulation is that we have an edge weighted graph $G = (V,E)$ which is bicolored so $V = A \cup B$ (note the coloring need not be proper, i.e. $G$ doesn't have to be bipartite). We are given an integer $k$ and want to find a minimum weight cycle (or alternatively path) which contains all vertices in $A$ and at most $k$ vertices in $B$.

Has this problem been studied somewhere? Does it have a name or fit inside a known generalized TSP? Or maybe there is some reduction to known version of TSP?

When $k=0$ we can delete vertices in $B$ along with all edges incident to them and we have the usual TSP.

**Tags:** reference-request, graph-theory, graph-algorithms, co.combinatorics, optimization

---

## 1 answers

### Answer by username_1 on 2021-05-20. Score: 4 | Accepted answer

As TSP is an optimization problem, there are not many variants of it (that I know of) that add hard constraints to the formulation. But if I have understood correctly, your problem is a special case of (a variant of) the Prize-Collecting Travelling Salesman Problem (PCTSP), which seems to be introduced in [1] *(NB: Technical report, written on typewriter. Hard to read)*:

Given a graph $G$ and a *prize* $w\_v$ and a *penalty* $p\_v$ for each vertex $v \in G$, you are asked to construct a tour that minimizes the cost of travelling, plus the penalty for every vertex you do *not* visit. In addition, you have the constraint that the combined prize for every vertex you *do* visit must be higher than some prescribed sum $W$.

If you are allowed to put negative values on your prizes, your problem can be formulated as a PCTSP this way:

* Let $p\_v = 0$ for every $v\in V$
* Let $w\_a = n$ for every $a\in A$
* Let $w\_b = -1$ for every $b\in B$
* Let $W = n\cdot |A| - k$

It's worth it to add that having shorter routes often will lead to cheaper tours anyway. For example, if $G$ is metric, then you can just solve TSP on $G[A]$, as visiting any vertices in $B$ will be considered a detour.

[1] *Balas, Egon*, [**The prize collecting traveling salesman problem**](http://dx.doi.org/10.1002/net.3230190602), Networks 19, No. 6, 621-636 (1989). [ZBL0676.90089](https://zbmath.org/?q=an:0676.90089).


---

