<p>The class of cubic Hamiltonian graphs is well studied class. I came across the fact that <a href="http://www.sciencedirect.com/science/article/pii/S0012365X10001974" rel="nofollow">independent set problem is $NP$-complete</a> when restricting input to cubic Hamiltonian graphs. I am interested in other hard problems on this class.</p>

<blockquote>
  <p>Which $NP$-complete problems on cubic graphs remain hard when restricted to cubic Hamiltonian graphs?</p>
</blockquote>

<p>A survey of such hard problems would be very nice.</p>

<p><strong>Motivation</strong></p>

<p>Given two NP-complete problems on a restricted graph class, I would like to understand the intractability boarderline when we further restrict input instances.</p>

<p><strong>UPDATE</strong>: I am not interested in decision version of optimization problem such as clique problem (or maximum independent set). However, Dominating Clique problem is the kind of $NP$-complete problem that would interest me if it was hard on cubic Hamiltonian graphs. Dominating clique in graph $G(V,E)$ is a dominating set of $V$ and a clique of $G$. </p>

<p>Dominating clique problem is interesting for <em>me</em> because the problem definition does not contain a parameter ( unlike clique or MIS for which we must specify the size of the required solution). </p>

CC BY-SA 3.0
2014-12-29T20:47:42.817Z
Google search did not help.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-12-29T21:14:27.207Z
Just a note: deciding if another Hamiltonian cycle exists in cubic graphs is NPC (when the first one is given as part of the input), for cubic Hamiltonian graphs, the decision version is in P (always yes), but (I think) it is still an open problem if finding it is in FP.
Marzio De Biasi
CC BY-SA 3.0
2014-12-29T22:18:43.403Z
@MarzioDeBiasi I think you mean "deciding if another Hamiltonian cycle exists in general graphs is NPC" in your first sentence.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-12-30T08:15:20.123Z
Mmm ... you're right, I didn't find anything about second Hamiltonian cycle on cubic graphs. But it should be NPC on graphs of max degree 8 (see [this construction](http://cstheory.stackexchange.com/questions/20538/co-np-completeness-of-minimal-tsp-tour)), and perhaps with some efforts it can be reduced to second HC problem on regular graphs with degree $c$ for some $c \leq 8$.
Marzio De Biasi
CC BY-SA 3.0
2014-12-30T16:40:02.063Z
Downvoters: Try being objective and fair and leave a comment to improve the question if you spot a problem.
Mohammad Al-Turkistany
<cc.complexity-theory><graph-theory>
$NP$-complete problems on cubic Hamiltonian graphs
Mohammad Al-Turkistany
# $NP$-complete problems on cubic Hamiltonian graphs

(Asked by: username_0 on 2014-12-29)

The class of cubic Hamiltonian graphs is well studied class. I came across the fact that [independent set problem is $NP$-complete](http://www.sciencedirect.com/science/article/pii/S0012365X10001974) when restricting input to cubic Hamiltonian graphs. I am interested in other hard problems on this class.

> Which $NP$-complete problems on cubic graphs remain hard when restricted to cubic Hamiltonian graphs?

A survey of such hard problems would be very nice.

**Motivation**

Given two NP-complete problems on a restricted graph class, I would like to understand the intractability boarderline when we further restrict input instances.

**UPDATE**: I am not interested in decision version of optimization problem such as clique problem (or maximum independent set). However, Dominating Clique problem is the kind of $NP$-complete problem that would interest me if it was hard on cubic Hamiltonian graphs. Dominating clique in graph $G(V,E)$ is a dominating set of $V$ and a clique of $G$.

Dominating clique problem is interesting for *me* because the problem definition does not contain a parameter ( unlike clique or MIS for which we must specify the size of the required solution).

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_0**: Google search did not help.  
> **username_1**: Just a note: deciding if another Hamiltonian cycle exists in cubic graphs is NPC (when the first one is given as part of the input), for cubic Hamiltonian graphs, the decision version is in P (always yes), but (I think) it is still an open problem if finding it is in FP.  
> **username_0**: @MarzioDeBiasi I think you mean "deciding if another Hamiltonian cycle exists in general graphs is NPC" in your first sentence.  
> **username_1**: Mmm ... you're right, I didn't find anything about second Hamiltonian cycle on cubic graphs. But it should be NPC on graphs of max degree 8 (see [this construction](http://cstheory.stackexchange.com/questions/20538/co-np-completeness-of-minimal-tsp-tour)), and perhaps with some efforts it can be reduced to second HC problem on regular graphs with degree $c$ for some $c \leq 8$.  
> **username_0**: Downvoters: Try being objective and fair and leave a comment to improve the question if you spot a problem.  

---

## 0 answers

