702 views

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?

1. Both DHAM$_3$ and SHAM$_3$ are NP-hard
2. SHAM$_3$ is NP-hard, but DHAM$_3$ is not
3. DHAM$_3$ is NP-hard, but SHAM$_3$ is not
4. Neither DHAM$_3$ nor SHAM$_3$ is NP-hard
recategorized | 702 views
0

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)

edited by
0
|V| is divisible by 3 in both the problems. The difference between DHAM and SHAM is that one is about finding if the Hamiltonian cycle exist and the other one is about finding that cycle.
0
$SHAM_3$: "finding a Hamil..." does not sound as a decision problem. Isnt it? Yes finding if Hamiltonian circuit exists or not is NP-Complete and hence NP-Hard...Am I write?
0

SHAMcan be reduced to DHAM3 which is a decision problem. So it must be at least as hard as DHAM3.

0
really ? changing non decision problem into decision problem ?
0
@Mahesha999 Your are correct, SHAM is not really a decision problem and is not eligible for NP-hard or NP-complete.