Algorithm: Removing as few elements as possible from a set in order to enforce no subsets
algorithm, subset
Solution
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 (A1, A2, ... An), then remove that from `B`. Unfortunately, finding the MHS is an NP-complete problem. Knowing that though, you have a few options:
- If your data set is small, do the obvious brute-force solution
- Use a probabilistic algorithm to get a fast, approximate answer (see this PDF)
- Run far, far away in the opposite direction
Problem
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?