5
$\begingroup$

I need to prove as an exercise that the following problem is NP-Complete:

  • Given a graph and an already existing Hamiltonian Circuit in that graph, decide if the graph has another Hamiltonian Circuit

For the proof I can use the NP-Completeness proof of the Hamiltonian Circuit Problem. I suppose I must reduce the Hamiltonian Circuit Problem to this one, but I can't see how. By the way, the reduction must be done in logarithmic space (L), not in polynomial time (P).

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.