GATE 2013
April 5, 2025GATE 2013
April 5, 2025GATE 2013
|
Question 18
|
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, 2 and 3
|
|
|
1 and 2 only
|
|
|
2 and 3 only
|
|
|
1 and 3 only
|
Question 18 Explanation:
Note: Out of syllabus.
1. Detecting cycle in a graph using DFS takes O(V+E) = O(V2)
Here, for complete graph E <= V2. So, It runs in polynomial time.
2. Every P-problem is NP because P subset of NP (P ⊂ NP)
3. NP – complete ∈ NP.
Hence, NP-complete can be solved in non-deterministic polynomial time.
1. Detecting cycle in a graph using DFS takes O(V+E) = O(V2)
Here, for complete graph E <= V2. So, It runs in polynomial time.
2. Every P-problem is NP because P subset of NP (P ⊂ NP)
3. NP – complete ∈ NP.
Hence, NP-complete can be solved in non-deterministic polynomial time.
Correct Answer: A
Question 18 Explanation:
Note: Out of syllabus.
1. Detecting cycle in a graph using DFS takes O(V+E) = O(V2)
Here, for complete graph E <= V2. So, It runs in polynomial time.
2. Every P-problem is NP because P subset of NP (P ⊂ NP)
3. NP – complete ∈ NP.
Hence, NP-complete can be solved in non-deterministic polynomial time.
1. Detecting cycle in a graph using DFS takes O(V+E) = O(V2)
Here, for complete graph E <= V2. So, It runs in polynomial time.
2. Every P-problem is NP because P subset of NP (P ⊂ NP)
3. NP – complete ∈ NP.
Hence, NP-complete can be solved in non-deterministic polynomial time.