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.