Algorithm: Removing as few elements as possible from a set in order to enforce no subsets

Question

I got a problem which I do not know how to solve:

I have a set of sets A = {A_1, A_2, ..., A_n} and I have a set B.

The target now is to remove as few elements as possible from B (creating B'), such that, after removing the elements for all 1 <= i <= n, A_i is not a subset of B'.

For example, if we have A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5}, and B={1,2,3,4,5}, we could e.g. remove 1 and 2 from B (that would yield B'={3,4,5}, which is not a superset of one of the A_i).

Is there an algorithm for determining the (minimal number of) elements to be removed?

Answer 1

It sounds like you want to remove the minimal hitting set of A from B (this is closely related to the vertex cover problem).

A hitting set for some set-of-sets A is itself a set such that it contains at least one element from each set in A (it "hits" each set). The minimal hitting set is the smallest such hitting set. So, if you have an MHS for your set-of-sets A, you have an element from each set in A. Removing this from B means no set in A can be a subset of B.

All you need to do is calculate the MHS for (A₁, A₂, ... A_n), then remove that from B. Unfortunately, finding the MHS is an NP-complete problem. Knowing that though, you have a few options:

1. If your data set is small, do the obvious brute-force solution
2. Use a probabilistic algorithm to get a fast, approximate answer (see this PDF)
3. Run far, far away in the opposite direction