patternMinor
A problem on sets
Viewed 0 times
problemsetsstackoverflow
Problem
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?
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?
Solution
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\}$.
Context
StackExchange Computer Science Q#115927, answer score: 2
Revisions (0)
No revisions yet.