Showing party invitation problem is np-complete

Question

Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party. Depending on how much you like housemate $i$, you pick an integer $m_i$ indicating the minimum number of people on $i$'s list that you'll invite. Having selected these values $m_i$ already, you'd like to know whether it is possible to invite at most $n$ people to your party such that for each housemate~$i$, at least $m_i$ of the people in $P_i$ are invited. We call this the Party Invitation problem. Prove that Party Invitation is NP-Complete.

I am not really sure which problem to reduce from and how to construct the reduction. Thank you

Answer 1

Simple party invitation problem. Suppose there are $m$ housemates decide to throw a party. Each housemate $i$ specifies a group of people $P_i$ who could be invited, $1\le i\le m$. Is it possible to invite at most $k$ people to the party such that at least one person in $P_i$ for each $i$ is invited?

It is enough to show the simple party invitation problem is still NP-Complete, which is, in fact, true.

Let's try to do some pattern matching between the simple party invitation problem and the set cover decision problem.

In set cover, we are given many sets, and we want to find some sets that satisfy some constraints. In simple party invitation, we are given many persons, and we want to find some persons that satisfy some constraints. Hence it seems that a set among the given sets should correspond to a person that could be invited. (Yes, a set corresponds to a person, which might be counterintuitive and which might be why this problem is not immediate to solve.)

What about the constraints? In set cover, we want to find some sets the union of which will cover all elements. In simple party invitation, we want to find some persons to invite so that every lists of people will be covered, that is, there is at least one person invited in each list. It looks like an element in set cover corresponds to a list of persons in simple party invitation. (Again, an element corresponds to a list, which might not be straightforward and which might be why this problem is not immediate to solve.) The fact that an element is a member of a given set in set cover corresponds to the fact a list of persons contains a given person.

You take it from here.

You could also reduce the hitting set problem to the simple party invitation problem, which might be clearer intuitively if you are familiar with the former.

---

_{For the pattern matching part, I am following the great teaching style in this answer of Yuval.}