algorithm - Path finding given vertex constraints

Question

I'm going to give the general case of this problem, because this is the 2nd time I've seen something that can be reduced to this and I haven't been able to find anything better than checking every path.

Suppose we have a directed graph G with vertices V such that there are no cycles and no self-edges. Additionally, each vertex has a color. Find the longest path starting from a given vertex such that the path goes through at most 1 vertex of each color.

I've implemented what is essentially depth-first search by removing all vertices of the added vertex's color in the recursive step, and I'm wondering if there's a better way to do it. The issue I keep running into is that storing past results is difficult because of the color restriction, so shortest path algorithms like Dijkstra's don't give the right result.

Answer 1

The answer to you problem is No.

If you assign each vertex with distinct color, your problem will be reduced to Hamiltonian path problem which is NP-hard.