Longest path in Complete Directed Graphs I searched in Google and checked similar questions on this site, but couldn't find an answer for my problem. I hope this place is appropriate for my problem.
The problem is formulated as follows:

We are given a weighted digraph with the following properties:

The weights are real numbers

Each vertex has a directed edge into every vertex, but without self-loops (i.e. the graph is complete, each vertex has |V|-1 in and out degree)

The weight for some edge $X \rightarrow Y$ is not necessarily the same as for $Y \rightarrow X$ (therefore we can't treat the graph as an undirected graph)


We are also given a source s and a sink t.
The problem is to find the longest path from s to t.
(Obviously the path should not contain any loops, and can contain at most |V|-1 edges)

Even though the problem is NP-hard and even finding a constant factor approximation is NP-hard for the general case, I wonder if for that kind of graphs we can do better.
The questions are:


Is the problem NP-hard?

If yes, how good can the problem be approximated? I would prefer fast running time over good results.

Do you know any good heuristics for the problem? (that work well in practice)



Any comment/answer/reference is appreciated. Thanks in advance!
Sage's implementation of it for instance :-)

http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path

Nathann