# Checking NP-completeness of the following problem(s)- Assigning candidates to departments

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.

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

You can solve this as a network flow feasibility problem, and so it is polynomial. The candidate nodes $$c\in\{1,\dots,n\}$$ have supply $$1$$, the department nodes $$d\in\{n+1,\dots,n+m\}$$ have demand $$r_d$$, and there is an arc from node $$c$$ to node $$d$$ if $$c \in C_{d-n}$$.