Re: Does it be an NP-hard problem to obtain a Hamiltonian path from Hamiltonian Graph


Zhu Guohun wrote:
Let G be a undirected Hamiltonian graph,
(1)Does there be a polynomial time to obtain a Hamiltonian path from a
pari of vertex (Vs, Vt)?
(2)Does there be a polynomial time to obtain a Hamiltonian path from a
first of vertex Vs?

Does anyone know any reference above these problems, thank for any
comments.

I'm not sure I understand what exactly you're asking. It looks like (1)
is asking for an algorithm like:

INPUT: Two vertices s,t, and a graph G.
OUTPUT: A Hamiltonian path from s to t.

This problem is equivalent to the Hamiltonian cycle problem.

I have no idea what (2) is asking.

--- Christopher Heckman

.