3
$\begingroup$

Given a collection C of sets, with union U, find a choice function which chooses a distinct element from each of the sets such that the union of the singleton distinct elements is U.

As an example, if we have the collection {1,2,3,4},{0,2,3,4},{0,1,3,4},{0,1,2,4} and {0,1,2,3} we can choose 1,0,3,4,2 from each of the sets respectively.

Can this be reduced to some another canonical problem? Has it been addressed in the existing literature?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You can reduce your problem to maximum bipartite matching on the graph $G = ( U \cup C, E)$, where $E = \{ (u,c) \in U \times C \; : \; u \in c\}$.

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.