<p>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 <span class="math-container">$d$</span>. Then insert this gadget into this face onto edges <span class="math-container">$e,f,g$</span>, where <span class="math-container">$e$</span> and <span class="math-container">$f$</span> are adjacent, and <span class="math-container">$g$</span> is opposite to them. Since <span class="math-container">$e$</span> and <span class="math-container">$f$</span> 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 <span class="math-container">$g$</span> is on the opposite side of the face, the size <span class="math-container">$d$</span> will be almost halved. Here 'almost' means that this inserted gadget also has some size <span class="math-container">$c$</span>, so the new faces will have size at most <span class="math-container">$d/2+c$</span>. Repeating this gets rid of all faces whose size is more than <span class="math-container">$2c$</span>.</p>

CC BY-SA 4.0
2019-03-22T01:02:11.180Z
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!
Elle Najt
CC BY-SA 4.0
2019-03-22T01:04:42.520Z
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.
Elle Najt
CC BY-SA 4.0
2019-03-22T01:07:26.253Z
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.)
Elle Najt
CC BY-SA 4.0
2019-03-22T06:01:41.323Z
Go ahead!$~~~~$
domotorp
CC BY-SA 4.0
2019-04-28T23:48:14.003Z
When you attach the 3-input OR gadget to these edges, it also increases the number of edges in adjacent faces. So, if you have already reduced the faces in some region of the graph to size below $2c$, it's conceivable that they could be increased again when you start to process the other faces. It seems possible (but very annoying) to get around this by some careful bookkeeping, but do you see a reason why this maybe isn't an issue?
Elle Najt
CC BY-SA 4.0
2019-04-29T19:13:27.347Z
There are many standard methods to deal with this. For example, if you denote the size of face $i$ by $f_i$, then $\sum_i f_i^2$ will strictly decrease in every step (if you pick $d$ properly).
domotorp
CC BY-SA 4.0
2019-04-29T22:26:20.203Z
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. :-)
Elle Najt
CC BY-SA 4.0
2019-03-21T22:25:26.827Z
2019-03-21T22:25:26.827Z
domotorp
<p>Let <span class="math-container">$\mathscr{C}_d$</span> be the class of <em>cubic</em> 3-connected simple plane graphs, with face degree bounded by <span class="math-container">$d$</span>.</p>

<p>Is there any <span class="math-container">$d$</span> such that Hamiltonian cycle is <span class="math-container">$NP$</span> complete on <span class="math-container">$\mathscr{C}_d$</span>? If so, what is the smallest (known) <span class="math-container">$\mathscr{C}_d$</span> ?</p>

<hr>

<p>My thoughts:</p>

<p>I know <span class="math-container">$\mathscr{C}_3$</span> consists only of graphs isomorphic to <span class="math-container">$K_4$</span>, by an Euler's formula argument. So necessarily <span class="math-container">$d &gt; 4$</span>.</p>

<p><span class="math-container">$\mathscr{C}_4$</span> is already infinite, and the number of isomorphism types of size <span class="math-container">$\leq k$</span> 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 <span class="math-container">$2^m$</span> choices based on the next subdivision point being 'right' or 'left' of the previous one. So <span class="math-container">$\mathscr{C}_4$</span> is (to me) a plausible candidate.</p>

<hr>

<p>I know the following two closely related theorems:</p>

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

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

<p>2) Hamiltonian cycle is NP-complete on the class of 3-connected plane graphs with face degree <span class="math-container">$3$</span> (i.e. maximal plane graphs): <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdf" rel="noreferrer">http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdf</a></p>

<reference-request><np-complete>
$NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree?
Elle Najt
# $NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree?

(Asked by: username_0 on 2019-03-20)

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>

**Tags:** reference-request, np-complete

---

## 1 answers

### Answer by username_1 on 2019-03-21. Score: 2 | Accepted answer

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$.

> **Comments:**
> **username_0**: 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!  
> **username_0**: 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.  
> **username_0**: 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.)  
> **username_1**: Go ahead!$~~~~$  
> **username_0**: When you attach the 3-input OR gadget to these edges, it also increases the number of edges in adjacent faces. So, if you have already reduced the faces in some region of the graph to size below $2c$, it's conceivable that they could be increased again when you start to process the other faces. It seems possible (but very annoying) to get around this by some careful bookkeeping, but do you see a reason why this maybe isn't an issue?  
> **username_1**: There are many standard methods to deal with this. For example, if you denote the size of face $i$ by $f_i$, then $\sum_i f_i^2$ will strictly decrease in every step (if you pick $d$ properly).  
> **username_0**: 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. :-)  

---

