The Set Cover Problem, but instead of solving for when the Union of subsets of S is U, I want the union to be or contain a specific subset of U.

157 Views Asked by At

Summary

I wonder if there is a solution to a simpler (or at least less strict) version of the Set Cover Problem where instead of searching for the smallest subset of $S$ whose union is equal $U$, I instead seek the smallest subset of $S$ whose union is equal to or contains a specific subset of $U$.

Example

Let the universe, $U$, be $$U = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}$$ and the set $S$ (whose union equals $U$) be $$S = \{ \{ 1, 2, 3 \}, \{ 2, 6 \}, \{ 4, 5, 7 \}, \{ 8, 9, 10, 3 \}, \{ 9, 10 \} \}$$

Is there an algorithm to find the smallest subset $X$ of $S$ whose union equals (or contains all of), say, $B$ $$B = \{ 1, 2, 3, 4, 5 \}$$ (or any other specific subset of $U$) that is better than brute forcing all combinations and checking? $X$ must either contain all of or be equal to B.

(I'm not looking for the solution to this specific example, but an algorithm for the general case)

1

There are 1 best solutions below

0
On BEST ANSWER

There can't be any difference in the complexity of the "simpler" version, because it's clearly equivalent.

As above, say $S$ is a collection of subsets of $U$ with union $U$, and say $B\subset U$. Define $$S_B=\{E\cap B:E\in S\}.$$Then finding a subset of $S$ with union containing $B$ is the same as finding a subset of $S_B$ with union equal to $B$; this last is precisely an instance of the original SCP.