# Easy infinite subclass of cubic graphs for Hamiltonian cycle problem

I know that Hamiltonian cycle problem is $NP$-complete for 2-connected planar bipartite cubic graphs.

I'm interested in non-trivial infinite subclass of cubic graphs where the Hamiltonian cycle (path) problem is efficiently solvable. I tried the graph class database but could not find any such class graph.

Is there any easy infinite subclass of 2-connected cubic graphs for Hamiltonian cycle problem?

Motivation: Barnette's conjecture states that every 3-connected planar bipartite cubic graphs is Hamiltonian which implies that HC is in $P$ (if it is true). However, Feder and Subi proved if there is any non-Hamiltonian 3-connected planar bipartite cubic graph then HC is $NP$-complete for this graph class.

• I think that it would be interesting to study what happens for 3-connected cubic graphs $G = (V, E)$ in which the nodes are points of the infinite lattice and the corresponding induced grid graph is included in $G$ (i.e. for every pair of adjacent nodes $u,v$ in the grid, $(u,v) \in E$. Perhaps worth a question on cstheory. – Vor Jul 10 '14 at 12:19

Yes, there is an infinite class of 2-connected cubic graphs on which Hamilton Cycle has a polynomial-time algorithm. Further, there is a such a class that contains infinitely many Hamiltonian graphs and infinitely many non-Hamiltonian graphs, which I think is a decent definition of "non-trivial".

First, let $H_n$ be the union of a $2n$-cycle on vertices $\{1, \dots, 2n\}$ and the edges $\{(i, i+n)\mid 1\leq i\leq n\}$. $H_n$ is 3-regular, 2-connected and has an obvious Hamiltonian cycle.

Now, let $G$ be a 2-connected cubic graph that has no Hamiltonian cycle. Such a graph must exist, since the Hamiltonian Cycle problem is NP-complete on 2-connected cubic graphs, so must have both "yes" and "no" instances. Fix an edge $xx'\in G$. For any graph $H_n$ pick any edge $yy'\in H_n$ and let $H'_n$ be the graph made by taking $G\cup H_n$, deleting the edges $xx'$ and $yy'$ and adding edges $xy$ and $x'y'\!$.

$H'_n$ is 3-regular and 2-connected but I claim that it has no Hamiltonian cycle. Any Hamiltonian cycle $C$ in $H'_n$ must enter the copy of $G-xx'$ at $x$ and leave at $x'$ (or vice-versa). But then $C$ must contain a Hamiltonian path $P$ of $G-xx'$ that begins at $x$ and ends at $x'\!$. However, no such Hamiltonian path can exist, since $P\cup\{xx'\}$ would be a Hamiltonian cycle of $G$, but $G$ was chosen to have no Hamiltonian cycles.

So the desired class of graphs is $\mathcal{H} = \{H_n\mid n>1\}\cup\{H'_n\mid n>1\}$. It remains to show that the Hamiltonian Cycle problem can be solved in polynomial time for graphs in $\mathcal{H}$. Observe that, for every $n$, every edge of $H_n$ is on a 4-cycle (there are 4-cycles of the form $i$, $i+1$, $i+n+1$, $i+n$, $i$). However, the edges $xy$ and $x'y'$ are not on any 4-cycle of $H'_n$. We can test that every edge of a graph is in a 4-cycle in time $\mathcal{O}(n^4)$.

I edited to changed the construction slightly, with two benefits. First, the algorithm runs in time $\mathcal{O}(n^4)$ instead of $\mathcal{O}(n^{|V(G)|})$. Second, there's an actual correctness proof; the old algorithm relied on the assumption that $G-xx'$ is not a subgraph of any $H_n$, which was probably true but really needed to be proven.

• May be I am missing something, but your construction produces only non-Hamiltonian graphs (since $G$ is always non-Hamiltonian). – Mohammad Al-Turkistany Jul 8 '14 at 23:46
• $H_n$ is always Hamiltonian; $H'_n$ is always non-Hamiltonian. $\mathcal{H}$ contains both sets of graphs. – David Richerby Jul 8 '14 at 23:55
• So, your efficient algorithm must know in advance the size of the hidden non-Hamiltonian cycle. Is this a reasonable assumption when designing an efficient algorithm? – Mohammad Al-Turkistany Jul 9 '14 at 0:04
• Since you commented, I changed the construction to give an $\mathcal{O}(n^4)$ algorithm (one could probably do better), independent of the choice of $G$. But, in any case, the definition of the graph class depends on knowing what $G$ is so was perfectly reasonable to assume the algorithm knows what $G$ is. (The current algorithm no longer needs to know $G$.) – David Richerby Jul 9 '14 at 0:13