Given: Collection $C$ of Subsets of a finite set $S$, positive integer $K <=|C|$
Problem Statement: Is there a collection $B$ of subsets of $S$ with $|B| = K$ such that for each subset $c$ in $C$, there is a sub-collection in $B$ whose union is $c$ ?
This Set Basis Problem is NP-Complete.
If we enforce an additional constraint that $B$ is a subset of $C$, is the problem still NP Complete?
My assumption is yes, but I could not find any reference to this problem. Can anyone please point out to one?