Multiple choice

Which of the following statements are TRUE? (1) The problem of determining whether there exists a cycle in an undirected graph is in P. (2) The problem of determining whether there exists a cycle in an undirected graph is in NP. (3) If a problem A is NP-complete, there exists a non-deterministic polynomial time algorithm to solve A.

  1. 1, 2 and 3

  2. 1 and 2 only

  3. 2 and 3 only

  4. 1 and 3 only
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation
  1. Cycle detection using DFS:  O(V + E) = O(V2 ) and it is polynomial problem
    1. Every P-problem is NP (since P $\subset$ NP)
    2. NP–complete Î NP Hence, NP–complete can be solved in non-deterministic polynomial time

Keep practicing — related questions