Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V,E)…
GATE · 2006 · CS
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
- C.
DHAM3 is NP-hard, but SHAM3 is not
- D.
Neither DHAM3 nor SHAM3 is NP-hard
Attempted by 57 students.
Sign up free to check your answer
Sign up freeLoading lesson…