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?

Home / Engineering / Theory of Computation / Question

Mr. Dubey • 51.17K Points
Coach

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

(D) Neither DHAM3 nor SHAM3 is NP-hard

Correct answer : Option (A) - Both DHAM3 and SHAM3 are NP-hard

Discusssion

Related MCQs on Theory of Computation

Q. The best use of linear programming technique is to find an optimal use of

Q. Which one of the following is not a function of network layer?

Q. What is the average case complexity of bubble sort?

Q. How many cases are there under Master’s theorem?

Q. Which of the following is not Ubiquitous Device ?

Q. WPA2 is used for security in _______

Q. What is the purpose of performing cross- validation?

Q. Which of these best describes an array?

Q. What is the first octet range for a class A IP address?

Q. The process of MBO starts with -----.