Bissoy.com
Doctors Medicines MCQs Q&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.

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. Correct Answer 1, 2 and 3

The correct answer is option 1.

Key Points

BFS or DFS can be used to find whether there is a cycle in an undirected graph. For example, see DFS based implementation to detect cycle in an undirected graph. The time complexity is O(V+E) which is polynomial and it is a P problem. Every p problems are NP problem (since P⊂NP). So, statement 1 and statement 2 are true.

[ alt="F1 Raju Madhuri 29.05.2021 D3" src="//storage.googleapis.com/tb-img/production/21/05/F1_Raju_Madhuri_29.05.2021_D3.png" style="width: 220px; height: 136px;">

NP-Complete ⊂ NP, for every NP problem, has a non-deterministic polynomial-time algorithm. Hence statement 3 is true.

Hence the all the statements are correct

Related Questions

A nondeterministic finite automation with ε-moves is an extension of nondeterministic finite automation.
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
State true or false? Statement: If a problem X is in NP and a polynomial time algorithm for X could also be used to solve problem Y in polynomial time, then Y is also in NP.
Assume the statements S1 and S2 given as: S1: Given a context free grammar, there exists an algorithm for determining whether L (G) is infinite. S2: There exists an algorithm to determine whether two context free grammars generate the same language. Which of the following is true?
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true? I. if L4 ∈ P, then L2 ∈ P II. if L1 ∈ P or L3 ∈ P, then L2 ∈ P III. L1 ∈ P, if and only if L3 ∈ P IV. if L4 ∈ P, then L1 ∈ P and L3 ∈ P
Given below are two statements: Statement I: A genetic algorithm is a stochastic hill-climbing search in which a large population of states is maintained. Statement II: In nondeterministic environments, agents can apply AND-OR search to generate contingent plans that reach the goal regardless of which outcomes occur during execution. In the light of the above statements, choose the Correct answer from the options given below
Let S be an NP-complete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?
G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE? I. If e is the lightest edge of some cycle in G, then every MST of G includes e II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e 
A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.
Which of the following statements are true? (A) An algorithm may produce no output (B) An algorithm expressed in a programming language is called a computer program. (C) An algorithm is expressed in a graphical form known as a flowchart (D) An algorithm can have an infinite sequence of instructions. Choose the correct answer from the options given below: