Consider the following two problems on undirected graphs

Home » Theory of Computation » Theory of computation miscellaneous » Question

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?

1. a is in P and b is NP-complete
2. a is NP-complete b is in P
3. Both a and b are NP-complete
4. Both a and b are in P

Correct Option: A

NA