Question: Suppose you\'re helping to organize a summer sports camp, and the foll
ID: 3569264 • Letter: Q
Question
Question:
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 < m, is it possible to hire at most k of the counselors and have at least one counselor qualified in each of the n sports? We'll call this the Efficient Recruiting Problem.
Show that Efficient Recruiting is NP-complete.
Explanation / Answer
Answer : Here we have to show that Efficient Recruiting is NP:
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.
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.