Q58

MCQ2 marks, −0.5

Consider the following two problems on undirected graphs: $\alpha$ : Given $G(V, E)$ , does $G$ have an independent set of size |V| - $4$ ? $\beta$ : Given $G(V, E)$ , does $G$ have an independent set of size $5$ ? Which one of the following is TRUE?

(A)

$\alpha$ is in P and $\beta$ is NP-complete

(B)

$\alpha$ is NP-complete and $\beta$ is in P

(C)

Both $\alpha$ and $\beta$ are NP-complete

(D)

Both $\alpha$ and $\beta$ are in P

Loading…