I came up with a problem that's similar to the Set Cover problem but which I can't reduce down to any know problem. Does anyone have a good algorithm for solving this?
Given a set of elements U = {1, 2, ..., m}
(the universe) and a collection S
of n
sets whose union equals the universe, what's the smallest sub-collection of S that intersects to produce a single element?
For example:
U = {1, 2, 3, 4, 5}
S = {{1, 4}, {2, 4}, {5, 2}, {1, 4, 5}}
If we want the smallest intersection that produces 4, we would need to intersect at least 2 sets {1, 4}
and {2, 4}
.
The current naive algorithm I have to do this involves
- Choose a set with the desired element
- Iterate over all unchosen sets, try intersecting with them and see if the intersection produces less elements than the original set but still include the desired element
- For those that intersect and reduce the number of elements, we repeat the process with the intersected set recursively until we've tried all sets or we're down to the element
For a concrete application: I'm trying to find the minimum set of CSS classes on an HTML element that will select only that element.