Consider the following two problems on undirected graphs α : Given G(V, E),…

PYQ GATE 2005

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 β is NP-complete

  2. B.

    α is NP-complete and β is in P

  3. C.

    Both α and β are NP-complete

  4. D.

    Both α and β are in P

Attempted by 340 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…