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

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.

.

Relevant Pages