# How to extract a set $C$ that contains $N$ subsets of a set $B$, covers all elements of an external set $A$, but $N$ is minimal?

Let $A$ denote a set that contains a relatively large number of different strings. Let $S_i$ denote these strings.

Let $B$ denote a set of sets such that each subset contains a (relatively small, usually not greater than 100) number of different strings. Let $B_i$ denote these subsets.

The problem is the following: is it possible to have an efficient way to obtain a set $C$ that contains a minimal number of different subsets of $B$, but for each $n$, a subset of $B$ that contains a string $S_n$ will be present as a subset of $C$?

Example:

A = ["a", "b", "cd", "e", "eeff", "x", "y", "xyz"];
B = [
["aa", "dce", "n", "e", "f", "y"],
["aa", "b", "n", "e", "f", "y"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["b", "t", "a", "h22", "z"],
["i", "cd", "le8", "a", "t", "eeff", "f"],
["aaa0", "x", "b", "a", "t1", "s"],
["xyz", "a", "n"],
["b", "xyz", "n"],
["eeff", "xyz", "dce", "aa"],
],


We can find multiple possibilities here, e.g. a set with five subsets:

C = [
["aa", "dce", "n", "e", "f", "y"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["b", "t", "a", "h22", "z"],
["aaa0", "x", "b", "a", "t1", "s"],
["eeff", "xyz", "dce", "aa"],
]


(note that for each $x$ such that $0 \le x \le 7$, there is an element of $C$ that contains $A_x$), but the possible solution allows to have only four elements in $C$:

C =
["aa", "b", "n", "e", "f", "y"],
["aaa0", "x", "b", "a", "t1", "s"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["eeff", "xyz", "dce", "aa"]
]


Is it possible to have a relatively efficient method of solving such a problem? I only see a factorial-level complexity (testing each possible combination), which quickly becomes physically impossible to implement. But if $A$ contains millions of elements, and $B$ contains billions of elements, we need another solution...

## 1 Answer

If you delete all subsets in $B$ that contain no string from $A$, then this is exactly the (Minimum) Set Cover problem, which is NP-hard, meaning that almost certainly no efficient (that is, polynomial-time) algorithm exists.

Testing each possible combination can be done in $O(m2^n)$ time if there are $n$ sets in $B$ and $m$ elements in $A$, which is better than factorial time. (We don't care about the order of the subsets we select.)