2
$\begingroup$

All references I find about the ANOTHER HAMILTONIAN CIRCUIT problem:

Given a graph and a hamiltonian circuit on it, is there another hamiltonian circuit on it?

I was trying to reduce it to the hamiltonian circuit problem but I always need to add too many or too few circuits to the original one.

Am I going through the good direction? It seems to be very simple...

Edit

Papadimitriou's complexity book refers to its theorem 17.5 for the inspiration for this problem.

I think that a good way for the solution is to consider the graph proposed in Papadimitrious'enter image description here

One can for each node of the original graph, transform to the graph shown at the left image. Then, one can connect all these new graphs using the poles N and S and thus obtains a hamiltonian circuit. Then, one uses W and E to connect vertex that were connected in the original graph. In principle, one could connect W with W and E with E.

I only have one more doubt, what happens if the original graph is just a segment, that is, two vertex with a edge between them. My construction would give an extra hamiltonian circuit going from W1->E1->E2->W2->W1 even if the original one didn't have one!

Can you find any other counterexample? This was the solution given in my course and it seems to be partly wrong...

$\endgroup$
  • $\begingroup$ You need to reduce the Hamiltonian Circuit problem (or some other NP-hard problem) to this problem: That is, if you had a magic device for solving ANOTHER HAMILTONIAN CIRCUIT quickly, could you solve other hard problems with it too? $\endgroup$ – j_random_hacker Aug 31 '17 at 18:40
  • $\begingroup$ I take back my earlier claim that there was a trivial reduction! I don't see any obvious way. $\endgroup$ – j_random_hacker Aug 31 '17 at 22:36
  • $\begingroup$ @j_random_hacker I updated with what seems to be the correct reduction but still have doubts $\endgroup$ – Javier Sep 1 '17 at 13:37
3
$\begingroup$

This result is proved in the senior thesis The complexities of puzzles, cross sum and their another solution problems (ASP) by Takahiro Seta.

The systematic study of ASPs was initiated by Ueda and Nagao in their paper NP-completeness Results for NONOGRAM via Parsimonious Reductions. See also Takayuki Yato's master thesis, Complexity and completeness of finding another solution and its application to puzzles.

$\endgroup$
  • $\begingroup$ Yes, they prove a stronger result. $\endgroup$ – Yuval Filmus Aug 31 '17 at 21:33

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.