shortest path in color-weighted graphs

Question

I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum of the weights of the colors used. If we have for example a path A->B->C where A and C are red colored and B is blue colored, its length should count the weight of red only once (and the weight of the blue node)! I'm struggling to find an (efficient) algorithm that can do this. Dijkstra's algorithm or any greedy algorithm cannot work, because they require that a local optimum must be also a global optimum. Here, this is not the case because the weight of a vertex depends on the path to it. You could add vertecies for each combination of colors but this would add exponantially many vertecies.

It would be enough for me to find such an algorithm for DAGs.

Thank you very much for your help!

Answer 1

This problem seems to be NP-hard. A reduction from 3-SAT is left as an exercise, but here is a hint. The empty nodes are free, and then create a color for each literal and its negation. The cost is 1 for each. You can then visit a "clause" for free if and only if one of its literals is selected. Now, the cheapest s-t-path costs $n$ if and only if the formula is satisfiable.