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

Question

Quizplus · Accepted Answer

The problem of determining if a Hamiltonian cycle exists in a graph (DHAM3) is NP-hard because it is a special case of the general Hamiltonian cycle problem, which is known to be NP-hard. Similarly, finding a Hamiltonian cycle in a graph (SHAM3) is also NP-hard because solving it would also solve the decision problem (DHAM3), implying that both problems are NP-hard.

Consider a Graph G = (V, E) Where I V