Re: Complexity of Finding the longest simple path in a graph

Michal Brzozowski wrote: 
tomnab@xxxxxxxxx wrote:
[..]

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...



Yes, your problem is NP complete. You have to notice that if your
problem had a polynomial solution, then you could solve the
Hamiltonian (path) problem easily by asking "Is the length of the
longest simple path from vertex 1 to any other vertex equal to the
number of vertices?".

Hamiltonian path problem is known to be NP-complete.


Couldn't a graph contain an Hamiltonian path, but not one that starts at
vertex 1?

For example, consider a three vertex undirected graph with vertices 1,
2, and 3 and with edges {1,2} and {1,3}. 2-1-3 is a Hamiltonian path,
but each longest simple path from 1 to any other vertex contains only
two vertices.

Patricia
.