Complexity of Finding the longest simple path in a graph

Hello,

I'm a French researcher in the field of Petri Nets. For short, PNs are
a tool to model discrete event systems. The behavior of a PN can be
formulated into a reachability graph : a directed, connex graph, where
circuits may exist.

In the case of bounded PNs, the reachability graph is finite, and I
want to compute the longest simple path of this graph, starting from
one particular vertice. Note I do not know any "target" vertice.

Since I'm not really aware of graph theory, I'd like to know the exact
denomination of this problem, its complexity, and of course some
references about the corresponding results. While searching on the
internet, I found that :

* The search for an hamiltonian path in this type of graph is NP
complete (but in my case I do not want to use automatically the whole
set of vertices);
* The search for a longest path between two KNOWN vertices is NP
complete (with a reference to the HamPath Problem that I do not
understand since nothing in "longest path" means "all the vertices"
like in Hamiltonian pbs...)

I'd like to know if I have well understood the previous assertions, if
I can say that my problem is NP complete, and the corresponding
references and arguments...

Thanks for your comments, and please forgive my poor english &
knowlegde...

T. Bourdeaud'huy

.

Relevant Pages

  • Re: Complexity of Finding the longest simple path in a graph
    ... salesman problem / you can look for Kruskal and Prim's algo... ... > formulated into a reachability graph: ... Note I do not know any "target" vertice. ... > references about the corresponding results. ...
    (comp.theory)
  • Re: Calling destructor
    ... >> Something you can do, that will help, is to set references to null for ... As long as you hold references to an object, ... OP described how he had a large graph of objects and needed the ability to ... In such a scenario, setting a reference to the object to null ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Problem about Dijkstras Min Path Algorithm
    ... I used one vector that stated the number of edges connecting a vertice. ... with the help of auxiliary vector to state if a vertice was already used or not I think I managed to implement Dijkstra's algorithm. ... You now just need to convert your data in this format instead of using the adjacency matrix. ... P.S. - Graph theory is not exactly my field of work... ...
    (comp.soft-sys.matlab)
  • Re: maximal 3-colorable subset
    ... johank wrote: ... a optimisation variant of graph coloring that fixes the number ... # difficulties finding references that address such problems. ...
    (comp.theory)
  • Re: White House spins "The Commander Guy"
    ... References you ... That's the true test of science -- ... The graph shows a scatter anywhere between 110 and 130. ... science is to consider all data, and that scatter graph has more data ...
    (rec.sport.golf)