5
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Vor
    Jul 10, 2014 at 12:19

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ May be I am missing something, but your construction produces only non-Hamiltonian graphs (since $G$ is always non-Hamiltonian). $\endgroup$
    – Mohammad Al-Turkistany
    Jul 8, 2014 at 23:46
  • $\begingroup$ $H_n$ is always Hamiltonian; $H'_n$ is always non-Hamiltonian. $\mathcal{H}$ contains both sets of graphs. $\endgroup$
    – David Richerby
    Jul 8, 2014 at 23:55
  • $\begingroup$ 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? $\endgroup$
    – Mohammad Al-Turkistany
    Jul 9, 2014 at 0:04
  • $\begingroup$ 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$.) $\endgroup$
    – David Richerby
    Jul 9, 2014 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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