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?

$\endgroup$
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\}$.

$\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.