![Mcqmate logo](https://mcqmate.com/images/logos/logo-black.png)
![Mcqmate logo](https://mcqmate.com/images/logos/logo-white.png)
McqMate
Q. |
Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is |
A. | Only DHAM3 is NP-hard |
B. | Only SHAM3 is NP-hard |
C. | Both SHAM3 and DHAM3 are NP-hard |
D. | Neither SHAM3 nor DHAM3 is NP-hard |
Answer» C. Both SHAM3 and DHAM3 are NP-hard |
View all MCQs in
Theory of ComputationNo comments yet