Multiple choice

Which of the following problems is not considered to be in NP-complete?

  1. dominating set problem

  2. vertex cover decision problem

  3. Hamiltonian path problem

  4. subset sum problem

  5. graph isomorphism
Reveal answer Fill a bubble to check yourself
E Correct answer
Explanation

The graph isomorphism problem is suspected to be neither in P nor NP-complete, though it is in NP. This is an example of a problem that is thought to be hard, but is not thought to be NP-complete.

Keep practicing — related questions