<p>A decision variant, without the minimality condition, asking whether there is a set <span class="math-container">$B$</span> of size <span class="math-container">$n$</span> is called the set basis problem [SP7] in <em>Computers and Intractability: A Guide to the Theory of NP-Completeness</em> by Garey and Johnson. The NP-completeness of it was proved by Stockmeyer.</p>

CC BY-SA 4.0
2019-02-04T20:54:02.287Z
Indeed. And the graph-theoretic interpretation of the minimum number is known as bipartite dimension: https://en.m.wikipedia.org/wiki/Bipartite_dimension
Hermann Gruber
CC BY-SA 4.0
2019-02-01T12:26:39.957Z
2019-02-01T12:26:39.957Z
user6192
<p>Is this a known problem?</p>

<p>Given a set of sets <span class="math-container">$S$</span> find a set of sets <span class="math-container">$B$</span> s.t. each set in <span class="math-container">$S$</span> can be obtained through unions of some sets in <span class="math-container">$B$</span>. The set <span class="math-container">$S$</span> is already a solution but the objective is to find the smallest <span class="math-container">$B$</span>. </p>

<p>For instance <span class="math-container">$\{\{a,b\}, \{c\}, \{a,b,c\}\}$</span> can be obtained from <span class="math-container">$\{\{a,b\}, \{c\}\}$</span>.</p>

<p>Since it's somewhat similar to set-cover, I suspect it's NP-hard.</p>

<p><strong>Additional remark:</strong> <span class="math-container">$B$</span> does not have to be a subset of <span class="math-container">$S$</span>.</p>

<reference-request><np-hardness><set-cover>
Minimal generator for a set of sets
Mikolas
# Minimal generator for a set of sets

(Asked by: username_0 on 2019-01-31)

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

**Tags:** reference-request, np-hardness, set-cover


---

## 1 answers

### Answer by username_1 on 2019-02-01. Score: 7

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.

> **Comments:**
> **username_2**: Indeed. And the graph-theoretic interpretation of the minimum number is known as bipartite dimension: https://en.m.wikipedia.org/wiki/Bipartite_dimension  

---

