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!

$\endgroup$
  • 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 '11 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 '11 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 '11 at 21:36
  • $\begingroup$ The weight can be arbitrary. $\endgroup$ – George Jul 11 '11 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 '11 at 15:57
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

$\endgroup$
  • $\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 '11 at 19:53
  • $\begingroup$ I insist you should try first, if you did not :-) $\endgroup$ – Nathann Cohen Jul 12 '11 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 '11 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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