This question is for 25 points please help me in getting thi

This question is for 25 points please help me in getting this answered

Suppose you\'re helping to organize a summer sports camp, and the following problem comes up. The camp is supposed to have at least one counselor who\'s skilled at each of the n sports covered by the camp (baseball, volleyball, and so on). They have received job applications from m potential counselors. For each of the n sports, there is some subset of the m applicants qualified in that sport. The question is \'\'For a given number k

Solution

Efficient Recruiting is NP: Given a set of k counselors, it can be checked in polynomial time that at least one counselor is qualified in each of the n sports.
Vertex Cover is known to be NP-complete (8.16).
Vertex Cover P Efficient Recruiting: Suppose we have a black box for Efficient Recruiting and want to solve an instance of Vertex Cover. For our Vertex Cover Problem, we have a graph G=(V,E) and a number k, and need to find out if G contains a vertex cover of size (at most) k. We need to reduce the Vertex Cover Problem to an Efficient Recruiting Problem. We do this by assigning each counselor to a node and each edge represents some sport. Each counselor is qualified in the sports for which the sport edge is incident on their corresponding counselor node. Then we ask the black box for the Efficient Recruiting Problem if there is a subset of k counselors that are qualified in all sports.
The black box for Efficient Recruiting will return “Yes” the Vertex Cover Problem is “Yes”, i.e. graph G contains a vertex cover of size k.
The black box for Efficient Recruiting will return “Yes”: there is a subset of k counselors that are qualified in all sports, so every sport edge is incident on at least one node in the set of nodes corresponding to the counselor subset. Hence, this set of nodes is a vertex cover of size k.
The Vertex Cover Problem is “Yes”, i.e. graph G contains a vertex cover of size k. Then for the subset of counselors that are assigned to the nodes in the vertex cover, each sport edge is incident on at least one node in the vertex cover, so there is a subset of k counselors corresponding to the vertex cover nodes that are qualified in all sports. The black box for Efficient Recruiting will return “Yes”.
Vertex Cover Problem requires polynomial time to construct the problem as an Efficient Recruiting Problem and polynomial calls to the Efficient Recruiting Problem black box. Hence, Vertex Cover P Efficient Recruiting.
(8.14) If Y is an NP-complete problem, and X is a problem in NP with the property that Y P X, then X is NP-complete.
Thus, Efficient Recruiting is NP-complete.