5
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\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$
    – Elle Najt
    Commented Mar 22, 2019 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$
    – Elle Najt
    Commented Mar 22, 2019 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$
    – Elle Najt
    Commented Mar 22, 2019 at 1:07
  • $\begingroup$ Go ahead!$~~~~$ $\endgroup$
    – domotorp
    Commented Mar 22, 2019 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$
    – Elle Najt
    Commented Apr 29, 2019 at 22:26

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.