# NP-completeness of some problems on assigning candidates to departments

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.

• – D.W.
May 1, 2022 at 6:10

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$$).
• if you don't mind I was wondering if you could help me with a variation on this problem which I don't think can be reduced to a flow problem: It is similar to the above, except you disregard the $r_d$, and say that the departments want to hire all of the respective $C_d$. This might not be possible for all depts at once so the question becomes: is there an assignment that satisfies $k$ departments at once for a $k < m$? Is this new problem NP complete? Apr 29, 2022 at 19:41
• That problem is NP-complete by a reduction from exact 3-cover [Garey & Johnson, SP2]: in this problem you are given an universe $X$ of $3\eta$ elements and a collection $C$ of sets, where each sets contains exactly 3 elements from $X$. The goal is to decide whether there is a subset $C'$ of $C$ such that $\cup_{S\in C'} S =X$ (clearly $|C'|=\eta$). In your case the $n=3\eta$ candidates are the elements in $X$, $m=|C|$, and the generic $d$-th set in $C$ corresponds to the set $C_d$ for the $d$-th department. The goal is to satisfy $k=\eta$ departments (or, equivalently, hiring all employees). Apr 29, 2022 at 21:57