NP-completeness of some problems on assigning candidates to departments

Question

Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. A candidate can be assigned to at most one department (so not being assigned is possible). Each department $d$ is considering candidates in $C_d \subseteq \{1, 2, ... n\}$ (with possible overlap between departments), and that each department $d$ must hire exactly $r_d$ of the $|C_d|$ candidates it is considering. The problem is to find an assignment of candidates to departments.

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 3-SAT, 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 these 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.

Answer 1

Your problem is not $NP$-complete because it is not a decision problem and hence it is not even in $NP$. Moreover your problem is not $NP$-hard, unless $P=NP$. In fact, your problem can be solved in polynomial time.

To do so, create a bipartite graph $G=(U+V, E)$ where $U=\{1,\dots,n\}$ represents candidates and $V$ contains $r_d$ pairs $(d, 1), \dots, (d, r_d)$ for each department $d=1,\dots, m$. Intuitively $(d, j)$ represents the $j$-th position to be filled by department $d$. Finally, $E$ contains the edge $(i, (d,j))$ if and only if $i \in C_d$. (Notice that the size of $G$ is polynomial in the size of the instance since we can assume w.l.o.g. that $r_d \le |C_d| \le n$).

Your problem is now equivalent to finding a $V$-perfect matching of $G$. This problem can be solved in polynomial-time (for example by adding a "source" vertex $s$ adjacent to all vertices in $U$, a "target" vertex $t$ adjacent to all vertex in $V$, setting all edges capacities to $1$, and trying to push $\sum_{d=1}^m r_d$ units of flow from $s$ to $t$).