TSP Variant — Colored Path

Question

Recently I came up with a traveling-salesman-esque problem. As usual, we have $n$ vertices, and a weighted edge between any two vertices. However, each vertex is associated with a color, which may be repeated. Then, you are given a sequence of colors, and you want to find the shortest path that follows this sequence. If all vertices are the same color, this is the same as TSP. However, if all vertices are different colors, there is only one solution.

Is this variant at all studied? Let $c$ be the maximum number of vertices which are the same color. Is the decision problem this variant NP-complete for some fixed, $c$, or alternatively is there a simple way to solve the decision problem polynomially for any finite $c$? Alternatively, one can bound $k$, the mamximum amount of times a given color appears in your path.

For $k=1$, it is polynomial. WLOG we can assume the path goes through colors $1,2,3,\ldots,x$. For each vertex of color 1, we consider each edge to a vertex of color 2. We keep track of the shortest path from color 1 to each vertex of color 2. Rinse and repeat for each color. This only requires $|\mathrm{color}\ i||\mathrm{color}\ i+1|$ additions and comparisons to get the shortest paths to each vertex of color $i+1$.

Additionally, I realize $k$ only matters if it is less than $c$, so bounded $c$ is polynomial if bounded $k$ is polynomial and bounded $k$ is NP-Complete if bounded $c$ is NP-Complete.

Answer 1

In this answer we prove the colored path problem is NP-hard for $c\ge 7$. I don't know whether it is NP-hard for $2\le c\le 6$. Without loss of generality, we prove the NP-hardness for the Hamiltonian Path problem variant, i.e., asking whether there exists such a colored Hamiltonian path, insteand of the TSP variant.

We use the normal reduction from 3SAT (with $n$ variables and $m$ clauses) to Hamiltonian Path with the following changes:

1. For each variable, we only have $2m$ nodes: $v_1,v_2,\ldots,v_{2m}$. The $i$th clause corresponds to nodes $v_i,v_{i+1}$ and $v_{2m-i+1},v_{2m-i}$, i.e., if the $i$th clause contains the positive literal of this variable, we have the path $v_i\rightarrow c_i\rightarrow v_{i+1}$, where $c_i$ is the node corresponding to the $i$th clause; and if the $i$th clause contains the negative literal of this variable, we have the path $v_{2m-i+1}\rightarrow c_i\rightarrow v_{2m-i}$. In addition, we add a blank node $b_i$ between $v_i$ and $v_{i+1}$.

2. For each variable, for each $i$, we give $v_i$ and $v_{2m-i}$, $b_i$ and $b_{2m-i}$ the same color. In addition, we give $c_i, b_i, b_{2m-i}$ the same color if the variable is contained in the $i$th clause.

   The following graph is constructed from $(x_1\vee \neg x_2\vee x_3) \wedge(x_2\vee \neg x_3\vee \neg x_4)$. The number above a node represents its color.

3. We remove the edges to the sink node $t$. Instead, we add paths that pass through the blank nodes that may potentially not be visited due to visits of clause nodes. In the example above, the added edges form the following structure.

In the example above, we ask whether there is a Hamiltonian path with colors 1-2-3-4-5-4-3-2-6-3-7-8-7-3-6-...-11-3-8-14. You can check this reduction indeed works.

Answer 2

It is NP-complete.

It is obviously in NP.

To show it is NP-hard, reduce TSP to your problem. Say you require to repeat a certain sequence of colors. Just take the TSP instance and replace edges by paths with the repeat pattern of colors. Then the only legal way to move from one vertex to the next is by traversing that path.