Question

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

• A. Both A and B are NP-hard
• B. A is NP-hard but B is not
• C. B is NP-hard but A is not
• D. Neither A nor B is NP-hard

Hint:

Modifying problem constraints (like divisibility) does not necessarily reduce complexity if the core problem remains NP-hard.

Answer 1

The Correct Option is A

- Finding a Hamiltonian cycle is a well-known NP-complete problem. Restricting the graph G to have |V| divisible by 3 does not reduce its computational complexity. - Determining if such a cycle exists in graphs is also NP-hard, as it involves solving the same Hamiltonian cycle problem. - Therefore, both A and B are NP-hard.