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.