Let $\mathscr{C}_d$ be the class of cubic 3-connected simple plane graphs, with face degree bounded by $d$.

Is there any $d$ such that Hamiltonian cycle is $NP$ complete on $\mathscr{C}_d$? If so, what is the smallest (known) $\mathscr{C}_d$ ?

My thoughts:

I know $\mathscr{C}_3$ consists only of graphs isomorphic to $K_4$, by an Euler's formula argument. So necessarily $d > 4$.

$\mathscr{C}_4$ is already infinite, and the number of isomorphism types of size $\leq k$ grow exponentially fast: once you have a triangle, you can subdivide two of its edges and connect them with an edge. You can also subdivide four sided faces by connecting opposite edges with a new edge. You can then subdivide a triangle into an m level pyramid, and subdivide the levels with vertical lines, which gives $2^m$ choices based on the next subdivision point being 'right' or 'left' of the previous one. So $\mathscr{C}_4$ is (to me) a plausible candidate.

I know the following two closely related theorems:

1) Hamiltonian cycle is NP-complete on the class of cubic, 3-connected simple plane graphs ( $\mathscr{C}_{\infty}$ in my notation): http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf

In addition, they show that they can force the girth to be at least 5. This is opposite from the spirit of my question.

2) Hamiltonian cycle is NP-complete on the class of 3-connected plane graphs with face degree $3$ (i.e. maximal plane graphs): http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdf


In the first paper which you link to (Garey-Johnson-Tarjan) they show how to construct a 3-input OR on Figure 6. This gadget has the property that it can link 3 edges with the only requirement that at least one of them needs to be used. So start from your original cubic 3-connected graph and suppose that it has a face larger than $d$. Then insert this gadget into this face onto edges $e,f,g$, where $e$ and $f$ are adjacent, and $g$ is opposite to them. Since $e$ and $f$ are adjacent, anyhow one of them had to be used in the original cubic graph, so the gadget will do nothing. On the other hand, since $g$ is on the opposite side of the face, the size $d$ will be almost halved. Here 'almost' means that this inserted gadget also has some size $c$, so the new faces will have size at most $d/2+c$. Repeating this gets rid of all faces whose size is more than $2c$.

  • $\begingroup$ I thought about doing something like this, but convinced myself that adding this gadget would allow you to take a shortcut across that face, potentially creating a Hamiltonian cycle where there wasn't one before. But looking at their local states again, it seems like that's not possible. I'm going to take a closer look again. Thank you! $\endgroup$ Mar 22 '19 at 1:02
  • $\begingroup$ Ok, I think you are right about this :-) - the presence of the xor in their gadget prevents the kind of situation I was worried about. $\endgroup$ Mar 22 '19 at 1:04
  • $\begingroup$ This will be used to strengthen a result in some paper, so if you do not mind then I would like to acknowledge your input on this. (Of course I'll assume responsibility for any errors.) $\endgroup$ Mar 22 '19 at 1:07
  • $\begingroup$ Go ahead!$~~~~$ $\endgroup$
    – domotorp
    Mar 22 '19 at 6:01
  • 1
    $\begingroup$ Thank you for sharing that idea! I think what you are saying is something like this: If possible, refine the largest face of size $> d$. For $d$ large enough, if you can do such a refinement, you will always decrease the sum of squares of face degrees. Continue doing this until you cannot decrease the sum of squares any further, at which point there cannot be any faces of degree $ > d$. This is much easier than what I had in mind. :-) $\endgroup$ Apr 29 '19 at 22:26

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.