1
$\begingroup$

I have a graph with nodes of various colors and weighted edges between them. I would like to find the least cost path that touches exactly one node of each color. Is this a known problem or reducible to a known problem? If not, can you point me to resources I could read on approaches to solving these types of problems? I call it TSP because although it's not visiting all nodes, it visits all nodes of a particular type.

As a concrete example, in the image below: enter image description here

The shortest path that touches all 3 colors would be A -> B -> C -> D at a cost of 4, but this touches a yellow node twice and so is invalid. The actual answer is C -> E -> F, at a cost of 5, since it touches all colors exactly once.

$\endgroup$
1
  • $\begingroup$ I realized I messed up the numbers and B -> C -> D is cheapest valid route but you get the idea. $\endgroup$
    – Jemmy
    Commented May 16 at 20:18

1 Answer 1

2
$\begingroup$

The problem is NP-hard. If each node has its own unique color, then you are asking for a solution to the Traveling Salesman Problem, which is NP-hard. Therefore, you should not expect any efficient algorithm to solve this problem.

It is similar to the set TSP problem, but not identical (there is one set per color, consisting of the vertices with that color).

You might be able to adapt existing methods to solve the TSP for your problem, e.g., using an ILP solver. See https://en.wikipedia.org/wiki/Travelling_salesman_problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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