Suppose youre helping to organize a summer sports camp and t

Suppose you’re helping to organize a summer sports camp, and the
following problem comes up. The camp is supposed to have at least
506

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.

Solution

Solution:

The Vertex Cover Problem:

Given a graph G and a number k , does G contain a vertex cover of size at most k . (Recall that a vertex cover V 0 V is a set of vertices such that every edge e E has at least one of its endpoints in V 0 .) Solution Ecient Recruiting is in NP, since given a set of k counselors, we can check that they cover all of the sports.

Suppose we had an algorithm A that solves Ecient Recruiting ; here is how we would solve an instance of Vertex Cover . Given a graph G = ( V,E ) and an integer k , we would dene a sport S e for each edge e and a counselor C v for each vertex v . C v is qualied in sport S e if and only if e has an endpoint equal to v . Now if there are k counselors that, together, are qualied in all sports, the corresponding vertices in G have the property that each edge has an end in at least one of them; so they dene a vertex cover of size k . Conversely, if there is a vertex cover of size k , then this set of counselors has the property that each sport is contained in the list of qualications of at least one of them.