0
$\begingroup$

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...

$\endgroup$
3
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.