How to prove NP-completeness of this variant of the set cover problem?

Question

The problem exactly:

Suppose you're helping to organize a summer sports camp, and the following problem comes up. For each of the n sports offered at this camp, the camp is supposed to have at least two counselors who are skilled at this sport. They have received job applications from m potential counselors. For each of the n sports, there is some subset of m applicants qualified in that sport. The question is: For a given k < m, is it possible to hire at most k of the counselors and have have at least two qualified in each of the n sports?

So, you are given a set U of elements, a collection of S1, S2...SM subsets of U, and an integer k. The original vertex-cover problem asks if there exists a collection of <= k of these sets whose union is equal to U. This question seems to ask how would we prove this is NP-Complete if we instead had to find a collection of <=k of these sets whose union covered the elements in U at least twice.

My first thought was to try to reduce the set cover problem. I was going to try to extend it to make it have to cover the union twice, but have no idea how to do that.

My next thought was to use 3-SAT since everything comes from that it seems, but I will die of old age before I figure that out.

My question is, what problem should I try to reduce from? Any could I get a hint for a first step to take? I've never proved one of these before so I'm really lost. I've been staring at this problem for 3 hours now.

Answer 1

Your first guess is correct. You misinterpreted however the meaning of reductions. When we prove the hardness of a problem $A$ by a reduction from $B$, we aim to reduce $B$ to $A$ and hence, given an instance $I$ of $B$, we want to build an instance $I'$ of $A$ such that $I$ is a yes-instance if and only if $I'$ is.

Now by reducing set cover to your problem, given an instance $(U, \mathcal{F}, k)$ of set cover, where $U$ is the universe, $\mathcal{F} := \{F_1, \dots, F_m\}$ the collection of sets and $k$ the maximum number of sets in the answer. We build the instance $(U, \mathcal{F}', k')$ as follows. If $k$ equals 0, then we output No. Otherwise, if $U \in \mathcal{F}$, we output yes. Else, Let $\mathcal{F}' := \mathcal{F} \cup \{U\}$, which means we add a new set to the collection, namely the set consisting of the whole universe. We also set $k' = k + 1$. We claim the original insatnce has a solution of size $k$ for the set cover problem if and only if the new instance has a solution of size $k+1$ of your problem.

For the first direction, given a solution of size $k$ for thr set cover problem, add the new universal set to the solution to build a solution for your problem of size $k+1$. (Why does this work?)

Now the harder direction, given a solution for the built instance of your problem of size at most $k+1$, if the universal set is a part of thr solution, the we can remove it to get a solution for the original insatnce of set cover with size at most $k$. If the universal set is not present, then remove any set from the solution (since you can switch this set with the universal set getting back to the previous case).

By this far we proved the hardness of the problem. For the completeness proof, note that given a solution of size $k+1$, we can count for each element in the universe how many times it was covered in the solution in polynomial time. Hence we can proof a positive witness in polynomial time and the problem is NP-complete.