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).


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.