Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. Suppose each department $d$ is considering hiring some $C_d \subseteq \{1, 2, ... n\}$ candidates (with possible overlap between departments), and that each department $d$ must hire exactly $r_d$ of the $|C_d|$ many candidates it is considering. The problem is to find an assignment of candidates to departments such that (a) a candidate is assigned to at most one department (so not being assigned is possible), and (b) each department gets all the $r_d$ candidates from $C_d$ it is looking for.
The question: Is this a NP-complete problem?
My instinct is yes- it is clearly NP at least.
I am trying to look for a suitable NP-reduction; the NP-complete problems I am familiar with and expected to use are 3Sat, Independence Set (finding a maximal independent subset of vertices of a graph), Vertex Cover (finding a minimal vertex cover of a graph), Partition (partitioning a multiset into two subsets with equal sum) and 3-Coloring.
The most promising is 3-SAT I think, where I can make each literal a candidate and each clause a department.
So for instance if I have $(x_1 \lor \neg x_2 \lor x_3) \land (\neg x_4 \lor x_5)$
Then I will have $5$ candidates, $2$ departments each requiring one candidate and the first department, for instance looking from the candidate pool $\{x_1, x_3\}$ (not $x_2$ since the first clause has $\neg x_2$). This has two big problems in that I'm not sure what to do with the $\neg$ literals, and this may have overlap between clauses (which would cause a candidate being assigned to more than one apartment).
But then I'm not sure how I would use the other problems.
