Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Is this a known problem?
Given a set of sets $S$ find a set of sets $B$ s.t. each set in $S$ can be obtained through unions of some sets in $B$. The set $S$ is already a solution but the objective is to find the smallest $B$.
For instance $\{\{a,b\}, \{c\}, \{a,b,c\}\}$ can be obtained from $\{\{a,b\}, \{c\}\}$.
Since it's somewhat similar to set-cover, I suspect it's NP-hard.
Additional remark: $B$ does not have to be a subset of $S$.
A decision variant, without the minimality condition, asking whether there is a set $B$ of size $n$ is called the set basis problem [SP7] in Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. The NP-completeness of it was proved by Stockmeyer.
