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$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.