TSP with "enemy" nodes

Question

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.

Answer 1

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, Networks 19, No. 6, 621-636 (1989). ZBL0676.90089.