CODEWITHSUNDEEP
algorithmgraphgraph-theory
Titandrake
Titandrake

Reputation: 626

algorithm - Path finding given vertex constraints

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.

Upvotes: 1

Views: 395

Answers (1)

user1678380
user1678380

Reputation:

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.

Upvotes: 2

Related Questions