Set Basis Problem Variant reference for NP-Completeness?

Question

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?

Answer 1

The problem is in fact solvable in polynomial time.

Let $$C_0=\Bigl\{c\in C:c\supsetneq\bigcup_{\substack{c'\in C\\c'\subsetneq c}}c'\Bigr\}.$$

On the one hand, if $B\subseteq C$ has the property in the question, then $C_0\subseteq B$: since $c\in C_0$ cannot be written as the union of its proper subsets from $C$, a fortiori it cannot be written as a union of its proper subsets in $B$, hence the only possibility is $c\in B$.

On the other hand, $B=C_0$ does have the required property. We prove by induction on $|c|$ that any $c\in C$ is a union of a subcollection of $C_0$: if $c\in C_0$, this holds trivially; otherwise $c$ is the union of its proper subsets in $C$, which in turn can be written as unions of subcollections of $C_0$ by the induction hypothesis.

Thus, the problem is equivalent to $|C_0|\le K$, which can be checked in polynomial time.