Question
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
Answer: Option A
Was this answer helpful ?
1. Cycle detection using DFS: O(V + E) = O(`V^ 2`) and it is polynomial problem
2. Every P-problem is NP (since P `subset` NP)
NP complete `in` NP
Hence, NP-complete can be solved in non-deterministic polynomial time
Was this answer helpful ?
More Questions on This Topic :
Latest Videos
Latest Test Papers
Submit Solution