Follow Us :

Dynamic Programming 12

0. 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.

  • Option : A
  • Explanation :
    1. We can use “Depth First Search” Algorithm, to check it there is a cycle is an undirected graph. I t 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” in 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 A ∈ NP. 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.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *