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

Any comment/answer/reference is appreciated. Thanks in advance!

• 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, 2011 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, 2011 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, 2011 at 21:36
• The weight can be arbitrary. Jul 11, 2011 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, 2011 at 15:57

## 1 Answer

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

• Looks nice, but it uses MILP to solve my problem (since my graph is weighted), which can be slow. As I said, I prefer a fast heuristic, even if the result is not always good. Thanks anyway! Jul 11, 2011 at 19:53
• I insist you should try first, if you did not :-) Jul 12, 2011 at 6:59
• I will try it, but the problem is that I have to solve such a problem thousands of times (it will be used as a subroutine for another problem), so I don't think I can use it (I also need to call it via Matlab, but that problem is minor compared to the former). Jul 12, 2011 at 8:57