0
$\begingroup$

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!

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ 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). $\endgroup$
    – Marc Bury
    Jul 11, 2011 at 18:36
  • $\begingroup$ 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. $\endgroup$
    – George
    Jul 11, 2011 at 19:44
  • $\begingroup$ 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|. $\endgroup$
    – mhum
    Jul 11, 2011 at 21:36
  • $\begingroup$ The weight can be arbitrary. $\endgroup$
    – George
    Jul 11, 2011 at 21:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Jul 12, 2011 at 15:57

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – George
    Jul 11, 2011 at 19:53
  • $\begingroup$ I insist you should try first, if you did not :-) $\endgroup$
    – Nathann Cohen
    Jul 12, 2011 at 6:59
  • $\begingroup$ 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). $\endgroup$
    – George
    Jul 12, 2011 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.