Is it possible that the graph is actually a DAG? Otherwise, as the longest path problem is NP-C, it's starting to look like a very worrying issue, even though it's only 10 vertices long...