2
$\begingroup$

I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs.

If we instead ask about balanced Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane graphs, is the problem still NP complete?

My intuition is that this extra requirement shouldn't make the problem easier, but maybe this feeling is naive since after all it means that the reduction has to be more intricate.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Your teacher posed a trick question. Think about it for a little while, and you will hit the solution. $\endgroup$
    – Gamow
    Commented Dec 6, 2018 at 15:54
  • $\begingroup$ @Gamow Oh, it appears that they are always balanced (?). (Easy to prove from the fact that maximal planar graphs with n vertices always have the same number of edges... I'll write this out.) Thank you! $\endgroup$
    – Elle Najt
    Commented Dec 6, 2018 at 17:41

1 Answer 1

Reset to default
3
$\begingroup$

Yes, it is still $NP$ complete. This is because of:

Claim: All Hamiltonian cycles on maximal planar graphs are balanced.

Proof: This is a special case of Grinberg's theorem: https://en.wikipedia.org/wiki/Grinberg%27s_theorem

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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