1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $c$ is maximum vertices of any color in the graph, $k$ is maximum vertices colors in the path we ask to solve/do a decision problem for. (So paths don’t have to clover the whole graph $\endgroup$ – Zachary Hunter Aug 16 at 11:58
  • 1
    $\begingroup$ You can use the normal reduction from 3SAT to Hamiltonian Path with some minor changes. Roughly speaking, we add a blank node between every two adjacent nodes corresponding to a clause, and add paths from the original end note $t$ to the blank nodes to ensure each blank node is able to be visited even if you have gone to the corresponding clause node. Then we mark symmetric nodes the same color. This reduction makes $c=7$. A detailed description of this reduction is very verbose and maybe you or someone else can write it as an answer. $\endgroup$ – xskxzr Aug 17 at 4:07
  • 1
    $\begingroup$ Once you have proved the NP-completeness for directed graphs, you can prove the NP-completeness for undirected graphs by splitting each node into three nodes: an in-node, a mid-node and an out-node. $\endgroup$ – xskxzr Aug 17 at 4:09
  • $\begingroup$ wait, does this use 7 colors? I meant to ask about when no more than $c$ vertices share a given color. $\endgroup$ – Zachary Hunter Aug 17 at 4:38
  • $\begingroup$ @ZacharyHunter No I mean at most 7 vertices share a given color. $\endgroup$ – xskxzr Aug 17 at 5:14
2
+50
$\begingroup$

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.

enter image description here

  1. 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.

enter image description here

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry, in the TSP we are reducing to, what are vertices? Is there a vertex for each color? Is this supposed to be for the case of bounded $c$ or for general colorings? $\endgroup$ – Zachary Hunter Aug 16 at 13:47
  • $\begingroup$ TSP takes a graph, with vertices (cities) and weighted edges (can go from one city to the next with a given cost). $\endgroup$ – vonbrand Aug 16 at 14:09
  • $\begingroup$ I am familiar of what TSP is. However, I don’t understand how you you are taking a colored graph and colored path and turning into a normal TSP. Additionally, it seems like you are not considering bounded $c$ at all. As was stated in the question, if $c=n$, this is precisely TSP, so it’s only interesting if $c$ has some upper bound. $\endgroup$ – Zachary Hunter Aug 16 at 14:18
  • $\begingroup$ I finally understand exactly what you were doing. However, in this case, $c$ is not bounded by a constant, or even sub-linear function. any color will appear in each ``edge'' of general TSP, so if we could solve this example in constant time, the amount of time to solve a TSP with at most $c$ edges. $\endgroup$ – Zachary Hunter Aug 17 at 3:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.