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.

  • 1
    Your teacher posed a trick question. Think about it for a little while, and you will hit the solution. – Gamow Dec 6 at 15:54
  • @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! – Lorenzo Dec 6 at 17:41

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

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

Proof: Let $G$ be a maximal planar graph with a Hamiltonian cycle. Say $G$ has $n$ vertices.

Let $C = (x_1, \ldots, x_n)$ be the Hamiltonian cycle on $G$. Using sphere inversion, we can reflect the inside of $C$ to the outside and glue that to the original inside along C, to get a different maximal planar graph $G'$. The number of faces in $G'$ is twice the number of faces inside $C$. The number of vertices of $G'$ is also $n$. So $G'$ has $2n - 4$ faces, since it is maximal planar (because all faces are still triangles). Half of them are inside $C$, so $C$ always has $n - 2$ faces on the inside. The same logic can be applied to the number of faces on the outside of $C$. Thus $C$ is balanced.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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