Home / Engineering / Theory of Computation / Question


Mr. Dubey • 51.17K Points

Q.) 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. Which one of the following is true?

(A) Both DHAM3 and SHAM3 are NP-hard
(B) SHAM3 is NP-hard, but DHAM3 is not
(C) DHAM3 is NP-hard, but SHAM3 is not
(D) Neither DHAM3 nor SHAM3 is NP-hard
Correct answer : Option (A) - Both DHAM3 and SHAM3 are NP-hard



Login to discuss.