Take the 2-minute tour ×  Is finding a hamiltonian cycle as hard
as determining if one exists? Can a hamiltonian cycle be found
in polynomial time given an oracle for detecting hamiltonian
cycles?  share|improve this question add comment  1 Answer  up
vote 7 down vote accepted  Assume you have a method to detect
whether or not a graph $G$ with $v$ vertices and $e$ edges has a
Hamiltonian cycle in time $p(v,e)$ for some polynomial $p$. The
following method then actually finds such a cycle:  For each
edge: Remove the edge; check if the graph is still Hamiltonian;
if not, add the edge back, otherwise leave it deleted. Once we
have treated all edges, a cycle remains.  This makes $e$ tests
of time $\le p(v,e)$ each, hence the time is $\le e\cdot p(v,e)$
and still polynomial.  share|improve this answer add comment
Your Answer