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$
5
  • $\begingroup$ Google search did not help. $\endgroup$ Commented Dec 29, 2014 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$ Commented Dec 29, 2014 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$ Commented Dec 29, 2014 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$ Commented Dec 30, 2014 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$ Commented Dec 30, 2014 at 16:40

0

Your Answer

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

Browse other questions tagged or ask your own question.