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

Improve this question
$\endgroup$
1
  • $\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
    Commented Nov 22, 2017 at 22:12

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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