Consider the following two problems on undirected graphs α : Given G(V, E),…
GATE · 2005 · CS
Consider the following two problems on undirected graphs
α : Given G(V, E), does G have an independent set of size | V | - 4?
β : Given G(V, E), does G have an independent set of size 5? Which one of the following is TRUE?
- A.
α is in P and β is NP-complete
- B.
α is NP-complete and β is in P
- C.
Both α and β are NP-complete
- D.
Both α and β are in P
Attempted by 266 students.
Show answer
Correct answer: D
The worked solution is available to enrolled students.
Video solution available to enrolled students.
Explore the full course: Iocl Engineers Officers Grade A Paper 2
Loading lesson…