Finding Smallest Sub-Collection of Sets – Algorithm Guide

algorithmscss

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

  1. Choose a set with the desired element
  2. 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
  3. 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.

Best Answer

Unfortunately your task is NP complete.

It is obvious that all sets from your solution should contain that single element (lets name it x). Also it is obvious that sets which doesn't contain x can't be included in the solution, so lets agree that they won't be present in S.

Lets create a new collection of sets S' = {S'k | Sk∈S | S'k = U\Sk} (i.e. every set consists of those items from universe that it didn't contain initially). In other words S'k defines the elements from U that will be removed from the intersection if we take Sk.

Now in order to solve the task you should select the minimum number of sets from S' which will cover U. Which is the definition of Set Cover problem you've mentioned in the beginning.

Related Topic