# 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:

1. Is the problem NP-hard?

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

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

• It is NP-hard. You can easily reduce a variant of the directed hamiltonian path (DHP) problem to your problem by setting the weight of every edge in the input graph to $1$ and $-1$ to the other edges and ask if there is a longest path with weight at least $\vert V \vert -1$. The variant version of DHP gets also two vertices $s,t$ as start/end vertex for the path (this is also NP-hard). Jul 11 '11 at 18:36
• It most probably is NP-hard, but a directed hamiltonian path can be easily found; actually every sequence of |V| distinct vertices is a hamiltonian path. Jul 11 '11 at 19:44
• You're not looking for a directed Hamiltonian path in the new (weighted, complete, directed) graph, you're looking for a path with weight >= |V|.
– mhum
Jul 11 '11 at 21:36
• The weight can be arbitrary. Jul 11 '11 at 21:54
• i actually don't understand how this problem is different from longest path except for being perhaps harder. since the graph is complete and weighted with no restriction on the weights you can just set some weights to 0 and you have longest path in full generality. if you don't allow 0 weights, you can instead use arbitrary small weights $\epsilon$ in place of 0 and for all intents and purposes you get the same problem. Jul 12 '11 at 15:57