Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE?
A)Both FHAM and DHAM are NP-hard
B)FHAM is NP hard, but DHAM is not
C)DHAM is NP hard, but FHAM is not
D)Neither FHAM nor DHAM is NP hard

Question

Quizplus · Accepted Answer

Both FHAM and DHAM are NP-hard because determining if a Hamiltonian cycle exists (DHAM) is a well-known NP-hard problem, and finding a Hamiltonian cycle (FHAM) is at least as hard as determining if such a cycle exists, making it also NP-hard.

Let FHAM Be the Problem of Finding a Hamiltonian Cycle