# Bipartite graph matching with multiplicities

Let's say we have N people, each of them holds several colored cards (for each color and person pair the number cards held is no more than one). We want algorithm determine how to take exactly one card from each person (denote this set of taken cards S), so the following function would be maximal: number of colors satisfying condition - there is at least k cards of this color in S.

In case of k=1 it's well-known problem of maximal matching in bipartite graph.

In case of k>1 this "matching" must have vertices of degree k on on side of bipartite graph. (It can be reformulated as a problem of finding maximal disjunct covering subset of specific set of coverings (in general case i think it's NP-complete?).

Does anyone know if this problem for k>1 NP-complete or can be solved in polynomial time (specifically for k=2)?

• I found an old thread on set packing, which is this question for arbitrary k. Maybe there is some better thing for k=2? Nov 22 '17 at 22:12