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

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.

• (The un-edited problem statement appeared on chegg.com under homework-help.) Commented Nov 19, 2019 at 22:49

## 1 Answer

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.

• No. The last part is independent from the reduction. The reduction proves NP-hardness. You asked for NP-completeness proof which additionally includes the proof of memebership in NP, which is exactly what the last paragraph is for. Commented Nov 19, 2019 at 22:18
• So it has nothing to do with set cover it only deals with your problem. It only says given a solution of your problem, you can check in polynomial time if it is a solution and hence, we have a certificate that we can prove in polynomial time which is enough to prove a problem is in NP. Commented Nov 19, 2019 at 22:20
• I understand that, just not the reduction. What do you mean by "let us add a new set to the family containing the whole universe"? Commented Nov 19, 2019 at 22:27
• The instance we build for your problem is the same instance of the set cover problem with one additional set in the collection. This set is $U$ itself. We also increase k by one. Commented Nov 19, 2019 at 22:57
• Ok... I don't see how that solves it at all though. If we added a new set with the entire universe, then set cover would always pick that because its contains everything we need? I suppose I need to think about it more.. Commented Nov 19, 2019 at 23:01