Which of the following statements are TRUE? 1. The problem of determining…
2013
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.
- A.
1, 2 and 3
- B.
1 and 2 only
- C.
2 and 3 only
- D.
1 and 3 only
Attempted by 97 students.
Show answer & explanation
Correct answer: A
Correct answer: 1, 2 and 3 (all statements are true).
Statement 1: The existence of a cycle in an undirected graph can be decided in linear time using depth-first search or breadth-first search (O(V+E)), so the problem is in P.
Statement 2: Any problem in P is also in NP (solutions can be verified in polynomial time), so cycle detection is in NP as well.
Statement 3: NP-Complete problems are by definition in NP, so there exists a nondeterministic polynomial-time algorithm that decides any NP-Complete problem.
Key relationships: P is a subset of NP (P ⊆ NP), and NP-Complete membership implies membership in NP (hence solvable by a nondeterministic polynomial-time machine).