$\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$ 2 Sorted by: Reset to default

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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