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 279 students.
Sign up free to check your answer
Sign up freeLoading lesson…