Assignment problem with no cost

Question

I have a problem that I was able to conceptualize as following:

Problem

We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination of these people, I want to check if it is a diverse group.

A diverse group is a group that satisfies several requirements, each requirement is of the form "at least $k_i$ persons in the group belong to subset $S_i$". Here is the tricky part, one person can only be used to satisfy one requirement. As in, you can't use him/her for multiple requirements.

Example:

Given:

At least two people from Hispanic= {a,b,c}

At least two people from African={a,d,e}

Is the group {a,c,d} a diverse group?

The group {a,c,d} is not diverse because you cant count a as Hispanic and African. But, the group {a,c,d,e} is diverse because we have two Hispanics a and c and two African d and e.

Attempt:

I think this is an instance of the Assignment problem. The jobs are the ethnicity and we can put as many ethnicity as the requirement dictate. For example, if we need two Hispanic, then we put two Hispanic jobs. However there only some people are able to do a particular job. Is there a name for such a problem? any algorithms somewhere in the internet? If not how would the implementation look like?

This is my attempt so far:

I will construct a bipartite graph with the set of people $P$ on one hand and the set of ethnicity on the other $S$. We will put an edge between a person $p_i$ and an ethnicity $S_i$ if he/she belongs to the ethnicity. Now, we will modify the graph, for every ethnicity $S_i$ duplicate it $k_i$ times ($S_{i,1}, S_{i,2}, ... , S_{i,k_i}$). And add new edges accordingly. Find the maximum matching M of this graph.

Now, merge the $S_{i,j}$s into one $S_i$ and there you have a diverse group. However, a maximum matching is only a possible solution to to the problem. And my problem is a decision problem, I want to check if a given group is a solution or not.

Answer 1

Let $P$ be the set of people and $\mathcal{S}$ be the modified multi-set of subsets. By checking if an $\mathcal{S}$-saturated matching into $P$ exists (i.e. Hall's condition) you are indeed finding a diverse group. If you are checking that some group $P$ is a putative solution the procedure is the exactly the same.

This can be done quickly via the Hopcraft-Karp algorithm (as you don't have weights over edges) or by implementing this as a Max-flow LP and using a solver. I'm willing to bet the solvers will work much faster in practice.

Answer 2

Nicholas Mancuso gave a good response, but it doesn't actually answer the question --- it only outlined a way to generate diverse groups, not how to decide whether a group is diverse (outside of a throwaway sentence).

So, I will use the method described in their response to outline a decision algorithm:

Let the set you're trying to decide on be denoted as $S$. Let the set of ethnicities be $E$.

First, construct a graph from in the same way you described in your question:

1. Have a vertex $S_i$ for each element in $S$.
2. Then, for every ethnicity $E_i$ in $E$, have vertex $E_{i,j}$, for every $1 \le j \le k_i$.
3. If $S_i \in E_j$ (for every $S_i \in S$, and $E_i \in E$), then draw the edge $(S_i,\, E_j)$.

Then, find a maximum-cardinality matching using the Hopcroft-Karp algorithm.

If the number of edges (ie, the cardinality) of the matching is $\sum_{i=1}^{|E|} k_i$, then the group is diverse. Else, it is not diverse.