GATE CS 2013 Q.18 (CS Q.18): Turing Machines and Chomsky Hierarchy

Which of the following statements are TRUE?

The problem of determining whether there exists a cycle in an undirected graph is in P.
The problem of determining whether there exists a cycle in an undirected graph is in NP.
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

Official answer and solution

Solution

Assess graph cycle detection complexity and the relationship between complexity classes P, NP, and NPC.

Evaluate each statement:

Statement 1: 'The problem of determining whether there exists a cycle in an undirected graph is in P.'
- True. Using Depth First Search (DFS) or Breadth First Search (BFS), a cycle in an undirected graph can be detected by finding a back-edge in $O(V + E)$ deterministic polynomial time.
Statement 2: 'The problem of determining whether there exists a cycle in an undirected graph is in NP.'
- True. Since $P \subseteq NP$ , any problem that belongs to P is automatically in NP.
Statement 3: 'If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.'
- True. By definition, a problem is NP-complete if it is in NP and every problem in NP polynomial-time reduces to it. Belonging to NP means that there exists a non-deterministic polynomial-time algorithm (or a polynomial-time verifier) to solve it.

Thus, statements 1, 2, and 3 are all TRUE.

Final answer

Option (A)

Common trap

Thinking that because a problem is in P, it cannot be in NP, forgetting the fundamental set inclusion $P \subseteq NP$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.