1
$\begingroup$

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Are DHAM3 and SHAM3 $\mathcal{NP}$-hard?

What I tried is I proved that the problem of finding Hamiltonian cycle is in $\mathcal{NP}$ and that 3-SAT problem, which is $\mathcal{NP}$-Complete, is reducible to Hamiltonian cycle problem which makes it $\mathcal{NP}$-hard, but I am not sure what's the purpose of $|V|$ divisible by 3, does that change anything?

Improve this question
$\endgroup$
4
  • $\begingroup$ You might want to try reducing Hamiltonian cycle (which is NP complete) to SHAM3 and DHAM3. This would prove that those problems are NP-hard. $\endgroup$
    – adrianN
    Commented Jan 9, 2017 at 8:59
  • $\begingroup$ @adrianN yes, but what I am curious about is whether |V| being divisible by 3 is of any use. $\endgroup$
    – Rakesh K
    Commented Jan 9, 2017 at 9:08
  • 4
    $\begingroup$ The use is making you think of a good reduction from general graphs to graphs with |V| being a multiple of three, I think. $\endgroup$
    – adrianN
    Commented Jan 9, 2017 at 10:45
  • $\begingroup$ cs.stackexchange.com/q/68410/755 $\endgroup$
    – D.W. ♦
    Commented Jan 9, 2017 at 17:49

1 Answer 1

Reset to default
1
$\begingroup$

There is no "purpose" for the condition that the number of vertices be divisible by 3 – it is part of the problem statement. DHAM3 is the special case of DHAM in which the number of vertices is divisible by 3. In principle this might make the problem easier (a special case can only be easier), but in this case DHAM3 is also NP-hard (and so NP-complete), as you can show by reduction from DHAM.

The problem SHAM3 is not a decision problem and so not eligible to be NP-complete or NP-hard.

How do you show that DHAM3 is NP-hard by reduction from DHAM? You have to come up with an efficiently computable function $f$ that takes an instance $x$ of DHAM and outputs an instance $f(x)$ of DHAM3 in such a way that $x \in DHAM$ iff $f(x) \in DHAM3$. In other words, $f$ takes a graph $G$ and outputs a graph $f(G)$ whose number of vertices is divisible by 3, and moreover $G$ is Hamiltonian iff $f(G)$ is Hamiltonian.

The difficulty here is that the original graph $G$ might have a number of vertices which is not divisible by 3 (otherwise you can take $f(G) = G$). I'll let you figure out how to overcome this difficulty.

Improve this answer
$\endgroup$
2
  • $\begingroup$ so in case of SHAM3 or SHAM we cannot even say that it not NP-hard? How do we define hardness of non-decision problems? $\endgroup$
    – Rakesh K
    Commented Jan 10, 2017 at 3:43
  • $\begingroup$ The usual way is to associate some decision problem, though there are also several notions of hardness for search problems and function problems. $\endgroup$
    – Yuval Filmus
    Commented Jan 10, 2017 at 6:37

Your Answer

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

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