Q31

MCQ2 marks, −0.5

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?

(A)

Both DHAM $_3$ and SHAM $_3$ are NP-hard

(B)

SHAM $_3$ is NP-hard, but DHAM $_3$ is not

(C)

DHAM $_3$ is NP-hard, but SHAM $_3$ is not

(D)

Neither DHAM $_3$ nor SHAM $_3$ is NP-hard

Loading…