<p>Sage's implementation of it for instance :-)</p>

<p><a href="http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path" rel="nofollow">http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path</a></p>

<p>Nathann</p>

CC BY-SA 3.0
2011-07-11T19:53:24.293Z
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!
George
CC BY-SA 3.0
2011-07-12T06:59:11.730Z
I insist you should try first, if you did not :-)
Nathann Cohen
CC BY-SA 3.0
2011-07-12T08:57:34.047Z
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).
George
CC BY-SA 3.0
2011-07-11T18:53:34.810Z
2011-07-11T18:53:34.810Z
Nathann Cohen
<p>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.</p>
<p>The problem is formulated as follows:</p>
<blockquote>
<p>We are given a weighted digraph with the following properties:</p>
<ul>
<li><p>The weights are real numbers</p>
</li>
<li><p>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)</p>
</li>
<li><p>The weight for some edge <span class="math-container">$X \rightarrow Y$</span> is not necessarily the same as for <span class="math-container">$Y \rightarrow X$</span> (therefore we can't treat the graph as an undirected graph)</p>
</li>
</ul>
<p>We are also given a source s and a sink t.</p>
<p>The problem is to find the longest path from s to t.</p>
<p>(Obviously the path should not contain any loops, and can contain at most |V|-1 edges)</p>
</blockquote>
<p>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.</p>
<p>The questions are:</p>
<blockquote>
<ol>
<li><p>Is the problem NP-hard?</p>
</li>
<li><p>If yes, how good can the problem be approximated? I would prefer fast running time over good results.</p>
</li>
<li><p>Do you know any good heuristics for the problem? (that work well in practice)</p>
</li>
</ol>
</blockquote>
<p>Any comment/answer/reference is appreciated. Thanks in advance!</p>

CC BY-SA 3.0
2011-07-11T18:36:13.920Z
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).
Marc Bury
CC BY-SA 3.0
2011-07-11T19:44:43.520Z
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.
George
CC BY-SA 3.0
2011-07-11T21:36:31.843Z
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
CC BY-SA 3.0
2011-07-11T21:54:23.827Z
The weight can be arbitrary.
George
CC BY-SA 3.0
2011-07-11T23:39:53.033Z
Perhaps there is some misunderstanding of Marc Gillé's reduction? We begin with an arbitrary unweighted, directed graph G and ask "Does G have a directed Hamiltonian path?". We then construct a directed, weighted, complete graph H and ask "Does H have a path of weight >= |V|-1?". The construction ensures that the answer to the second question is yes iff the answer to the first is also yes. Unless I misunderstand, this should be a fairly straightforward reduction.
mhum
CC BY-SA 3.0
2011-07-12T09:00:14.933Z
I understand how Hamiltonian path can be reduced to Longest path. The point is that in my graph permutation of the vertices forms a hamiltonian path, therefore a Hamiltonian path can be found in O(|V|) time. I hope I did not misunderstood something.
George
CC BY-SA 3.0
2011-07-12T15:50:49.947Z
I believe you are misunderstanding the reduction: Marc shows that if you can find a *path of total weight $\geq |V|$* in the graph output by the reduction, then you can solve directed hamiltonian path in arbitrary unweighted directed graphs. whether you can find a hamiltonian path in the graph output by the reduction is irrelevant. note that an arbitrary permutation of the vertices will not be a path of total weight $|V|$ because many vertices could have weight -1. that is the whole point of the reduction
Sasho Nikolov
CC BY-SA 3.0
2011-07-12T15:57:25.557Z
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.
Sasho Nikolov
CC BY-SA 3.0
2011-07-12T17:12:33.510Z
You are right, I misunderstood the reduction given by Marc. I understood something totally different, but it is clear to me now. Thanks for your helpful comments!!! But I'm still looking for some good heuristic, for this specific problem. I have some ideas, but I would also like to see a few more.
George
<ds.algorithms><graph-algorithms>
Longest path in Complete Directed Graphs
George
# Longest path in Complete Directed Graphs

(Asked by: username_0 on 2011-07-11)

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!

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: 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).  
> **username_0**: 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.  
> **username_2**: 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|.  
> **username_0**: The weight can be arbitrary.  
> **username_2**: Perhaps there is some misunderstanding of Marc Gillé's reduction? We begin with an arbitrary unweighted, directed graph G and ask "Does G have a directed Hamiltonian path?". We then construct a directed, weighted, complete graph H and ask "Does H have a path of weight >= |V|-1?". The construction ensures that the answer to the second question is yes iff the answer to the first is also yes. Unless I misunderstand, this should be a fairly straightforward reduction.  
> **username_0**: I understand how Hamiltonian path can be reduced to Longest path. The point is that in my graph permutation of the vertices forms a hamiltonian path, therefore a Hamiltonian path can be found in O(|V|) time. I hope I did not misunderstood something.  
> **username_3**: I believe you are misunderstanding the reduction: Marc shows that if you can find a *path of total weight $\geq |V|$* in the graph output by the reduction, then you can solve directed hamiltonian path in arbitrary unweighted directed graphs. whether you can find a hamiltonian path in the graph output by the reduction is irrelevant. note that an arbitrary permutation of the vertices will not be a path of total weight $|V|$ because many vertices could have weight -1. that is the whole point of the reduction  
> **username_3**: 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.  
> **username_0**: You are right, I misunderstood the reduction given by Marc. I understood something totally different, but it is clear to me now. Thanks for your helpful comments!!! But I'm still looking for some good heuristic, for this specific problem. I have some ideas, but I would also like to see a few more.  

---

## 1 answers

### Answer by username_4 on 2011-07-11. Score: 2 | Accepted 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

> **Comments:**
> **username_0**: 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!  
> **username_4**: I insist you should try first, if you did not :-)  
> **username_0**: 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).  

---

