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


Patricia Shanahan wrote:
> Michal Brzozowski wrote:
> >
> > 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.
>

Yes, my mistake. You should check the longest path at each vertex.
Checking at 2 or 3 would reveal the Hamiltonian path.

.