Let SHAM3 be the problem of finding a Hamiltonian cycle

Home » Theory of Computation » Theory of computation miscellaneous » Question

Let SHAM₃ be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM₃ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

1. Both DHAM₃ and SHAM₃ are NP-hard
2. SHAM₃ are NP-hard but DHAM₃ is not
3. DHAM₃ is NP-hard, and SHAM₃ is not
4. Neither DHAM₃ nor SHAM₃ is NP-hard

Correct Option: A

There is a difference between SHAM₃ and DHAM₃ that SHAM₃ is used for finding a Hamiltonian cycle in a graph but DHAM₃ is the problem of determining if a graph exists in a Hamiltonian cycle. Also it is given that |V| is divisible by 3, hence the problem can be reduced from 3 SAT which further determines that SHAM₃ and DHAM₃ are NP hard.