"Sling Blade Runner": efficient algorithm to find chain of overlapping movie titles?

This problem is from the archived puzzle from ITA Software, Since the puzzle is retired I guess it is ok to discuss.

How long a chain of overlapping movie titles, like "Live and Let Die Another Day of the Dead Poet's Society", can you find?

I would like to know what is the best approach/algorithm to solve开发者_运维知识库 such puzzle.

This is a graph problem.

First you build a graph, where each vertex represents a movie. There is an edge (a,b) if the movie a end in the same word as the one with which the movie b starts.

Now you want to find the longest path in the graph. This is NP-complete problem, so it doesn't have polynomial solution. (wikipedia)