Prove NP-Complete. $n$ clubs, largest has $m$ members. Hall Capacity is of $k$ guests. List $k$ students s. t. every club has atleast one member.

Question

Question
Prove that this Problem is $\mathbb{NP-Complete}$ given that that the problem SATISFIABILITY is $\mathbb{NP-Complete}$.

A University has $n$ clubs, the largest of which contains $m$ members (students can be members of multiple clubs). The President of the University wishes to hold a dinner in honor of such student activities. Unfortunately, food hall can seat comfortably only $k$ guests. Can we construct a guest list of $k$ students such that every club and society has at least one member in attendance?

My Idea

1. We will try to use function $f$ (polynomial time reduction) to reduce the SATISFIABILITY problem to our problem so that we can proof it is NP-COMPLETE.
2. Composed of $n =a_1+a_2+a_3+......$
3. I draw a $3$ sets to visualize the problem lets say we have tree clubs called $a_1,a_2,a_3$ $a_1=x+y+z+m$
   $a_2=y+p+z+m$
   $a_3=m+z+n+o$
   and I try to create a $M'$ that will look
   ($a_1$ and $a_2$ and $a_3$) or ($a_1$ and $a_2$ and NOT $a_3$) or ($a_2$ and $a_3$ and NOT $a_1$) or ($a_1$ and $a_3$ and NOT $a_2$)

This looks like SATISFIABILITY problem but I am not sure how should I answer this question.

Answer 1

It can be considered as the SET COVERING problem, which is known to be NP-complete.