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.

,

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.

A. 1, 2 and 3

B. 1 and 2 only

C. 2 and 3 only

D. 1 and 3 only

Correct Answer :

A. 1, 2 and 3

Explanation

 1) We can use "Depth First Search" Algorithm, to check it there is a cycle is an undirected graph. It we encounter any ''back edge" in "Depth first search" then given undirected graph has a cycle. Also, if there is a cycle in the undirected graph, we must encounter a "back edge" is DFS. And, DFS can be done in O (|E| + |V|) time for graph G = (V, E). So, it can is in F.
2) P < NP, so, it is also in NP.
3) NP-complete problem ANP. By, Definition Every problem in NP can be solved in polynomial time using non-deterministic turing machine.
So, Answer is (A) i.e. 1, 2, and 3 are true.