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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.