1

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.

Improve this question
2
  • I can come up with O(n*2^k) algorithm where n = max { |E|, |V|} and k = #colors. Note that this problem is very different from shortest path, because in here you are talking about longest path (which is generally NP-Hard problem, but the graph is a DAG, so there might be efficient solutions). Commented Oct 6, 2013 at 7:30
  • Backtracking (DFS) sounds good. There is no need to store past states, just colours that are visited with a current branch. Colour and vertex ordering is needed for a backtrecking, to know visit order from a current vertex. Solution is found when current branch has number of colours length. Commented Oct 6, 2013 at 20:24

1 Answer 1

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

That makes sense. For the record, what I ended up doing was depth first search with a globally updated top score and a upper-bound function to avoid traversing some nodes. It didn't improve time complexity, but in practice it was around 3x as fast.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.