Let SHAM$_3$ be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by $3$ and DHAM$_3$ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
Just mentioning additional information.
Dirac's theorem and Ore's theorem are necessary but not sufficient. So 'determining if a Hamiltonian cycle exists' is also NPH.
The only difference between SHAM and DHAM, in SHAM |V| is divisible by $3$.. which can be check in constant amount of time.. So the hardness of the two problem will the same... Next, finding hamiltonian cycle comes under NPC problem and NPC problem is a subset of NPH, so both are NPH..
So, option (A)
SHAM3 can be reduced to DHAM3 which is a decision problem. So it must be at least as hard as DHAM3.
Can we challenge this question?