8
$\begingroup$

Given a simple and connected graph $G=(V, E)$. I know it's NP-Complete to determine if $G$ has a Hamiltonian Cycle (HC). But if we know $G$ indeed contains an HC, can we find the cycle in poly-time?

$\endgroup$
14
$\begingroup$

No (or rather: no, unless P=NP).

If it were so, then there would be a concrete polynomial $p$ that bounded the running time of such an algorithm. Therefore you would be able to detect whether a graph has a Hamiltonian cycle by lying to the algorithm: Claim that the graph has a Hamiltonian cycle, run it for $p(n)$ steps, and then check whether by then it has printed a correct cycle or not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.