3
$\begingroup$

The class of cubic Hamiltonian graphs is well studied class. I came across the fact that independent set problem is $NP$-complete 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).

$\endgroup$
  • $\begingroup$ Google search did not help. $\endgroup$ – Mohammad Al-Turkistany Dec 29 '14 at 20:47
  • 3
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Dec 29 '14 at 21:14
  • 1
    $\begingroup$ @MarzioDeBiasi I think you mean "deciding if another Hamiltonian cycle exists in general graphs is NPC" in your first sentence. $\endgroup$ – Mohammad Al-Turkistany Dec 29 '14 at 22:18
  • 2
    $\begingroup$ 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), and perhaps with some efforts it can be reduced to second HC problem on regular graphs with degree $c$ for some $c \leq 8$. $\endgroup$ – Marzio De Biasi Dec 30 '14 at 8:15
  • 4
    $\begingroup$ Downvoters: Try being objective and fair and leave a comment to improve the question if you spot a problem. $\endgroup$ – Mohammad Al-Turkistany Dec 30 '14 at 16:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.