1
$\begingroup$

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)?

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

For k=2 it's Rainbow_matching, so it's NP-complete.

For all colors X make cliques of all people holding color X, and color it's edges with X.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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