Consider the following computational problem.
The CS department needs a committee to select the department's head. The committee cannot include people who have "conflicts of interest" with each other. The input consists of
(a) the desired committee size,
(b) a list of all the professors, and
(c) a list of all pairs of professors that are conflicted.
The goal is to determine whether there's a conflict-free committee of that size.
Remarks: For this question, it is important to understand the definition of NP, and the definitions of some of the standard NP-complete problems (Vertex Cover, Set Cover, Independent Set, Hamiltonian Path, etc.)
a. Prove that this problem is in NP.
b. Prove that this problem is NP-complete.