2
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

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$).

$\endgroup$
4
  • $\begingroup$ I should've been clearer- it is a decision problem in that the question asks- "is there such an assignment?" $\endgroup$
    – Estaban
    Apr 29, 2022 at 19:23
  • $\begingroup$ But I understand your solution. Thanks! $\endgroup$
    – Estaban
    Apr 29, 2022 at 19:26
  • $\begingroup$ 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? $\endgroup$
    – Estaban
    Apr 29, 2022 at 19:41
  • $\begingroup$ 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). $\endgroup$
    – Steven
    Apr 29, 2022 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.