title: Weighted bipartite matching with constraints on degrees of vertices
body: <p>I have a problem that I was able to conceptualize as following:</p>
  <p>We have a set of <em>n</em> people. And <em>m</em> 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.</p>
  <p>A diverse group is a group that satisfies several requirements, each requirement is of the form &quot;at least <em>Ki</em> persons in the group belong to subset <em>Si</em>&quot;. 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.</p>
  <p>An example:</p>
  <p>Given:</p>
  <p>At least two people from Hispanic= {a,b,c}</p>
  <p>At least two people from Asian={a,d,e}</p>
  <p>Is the group {a,c,d} a diverse group?</p>
  <p>The group {a,c,d} is not diverse because you cant count <em>a</em> as Hispanic and Asian. But,
  the group {a,c,d,e,f} is diverse because we have two Hispanics a and c and two Asian d and e.</p>
  <h2>Attempt:</h2>
  <p>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.</p>
  <p>This is my attempt so far:</p>
  <p>I will construct a bipartite graph with the set of people <strong>P</strong> on one hand and the set of ethnicity on the other <strong>S</strong>. We will put an edge between a person <strong>p_i</strong> and an ethnicity <strong>S_i</strong> if he/she belongs to the ethnicity.
  Now, we will modify the graph, for every ethnicity <strong>S_i</strong> duplicate it <strong>k_i</strong> times (<strong>S_{i,1}, S_{i,2}, ... , S_{i,k_i}</strong>). And add new edges accordingly. Find the maximum matching M of this graph.</p>
  <p>Now, merge the <strong>S_{i,j}</strong> s into one <strong>S_i</strong> 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.</p>