<p>The complexity of enumerating maximal independent sets in graphs is the same as in bipartite graphs, so bipartiteness does not bring anything new. </p>

<p>You have an algorithm (with exponential space) in $O(|C|\cdot n^2)$, but no polynomial space algorithm that acheives this time complexity is known. The following paper <a href="http://www.sciencedirect.com/science/article/pii/S0166218X08004563" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0166218X08004563</a> is a good survey. </p>

CC BY-SA 3.0
2012-11-13T08:45:55.043Z
2012-11-13T08:45:55.043Z
M. kanté
<p>Given a family $\mathcal F$ of at most $n$ subsets of $\{ 1, 2, \dots, n \}$.
The union closure $\mathcal F$ is another set family $\mathcal C$ containing every set that can be constructed by taking the union of 1 or more sets in $\mathcal F$.
By $|\mathcal C|$ we denote the number of sets in $\mathcal C$.</p>

<p>What is the fastest way to compute the union closure?</p>

<p>I have showed a equivalence between the union closure and listing all maximal independent sets in a bipartite graph, therefore we know that deciding the size of the union closure is #P-complete.</p>

<p>However there is a way to list all maximal independent sets (or maximal cliques) in $O(|\mathcal C| \cdot nm)$ time for a graph with $n$ nodes and $m$ edges Tsukiyama et al. 1977.
But this is not specialized for bipartite graphs.</p>

<p>We gave an algorithm for bipartite graphs with runtime $|\mathcal C| \cdot \log |\mathcal C| \cdot n^2$ <a href="http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf" rel="nofollow">http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf</a></p>

<p>Our method is based on the observation that any element in $C$ can be made by the union of some other element of $C$ and one of the original sets.
Hence we will whenever we add an element to $C$ try to expand it by one of the $n$ original sets.
For each of these $n \cdot |C|$ sets we need to check if they are still in $C$. We store $C$ as a binary search tree, so each lookup takes $\log |C| \cdot n$ time.</p>

<p>Is it possible to find the union closure $\mathcal C$ in $O(|\mathcal C| \cdot n^2)$ time?
Or even in time $O(|\mathcal C| \cdot n)$?</p>

CC BY-SA 3.0
2012-11-11T16:27:17.880Z
In the equivalence that you've shown between union closure and maximal ind. sets in bipartite graphs, is the equivalence a bijection? Or in other words, in your algorithm for listing all miximal ind. sets of a bipartite graph, is $|C|$ the number of maximal ind. sets?
Vinayak Pathak
CC BY-SA 3.0
2012-11-11T16:33:21.023Z
Yes  it is a bijection so $|C|$ is the number of maximal independent sets. (note that the emptyset must be defined to be in $C$).
Martin Vatshelle
CC BY-SA 3.0
2012-11-11T18:08:41.073Z
While this is unlikely to help with your question, what you're asking is a special case of computing the upward closure of elements in a lattice, and I wonder if there are results from there that might be useful.
Suresh Venkat
CC BY-SA 3.0
2012-11-13T08:48:29.327Z
The survey I point to in my answer below gives some links with lattices.
M. kanté
<co.combinatorics><graph-algorithms><clique><independence>
Computing the union closure
Martin Vatshelle
# Computing the union closure

(Asked by: username_0 on 2012-11-10)

Given a family $\mathcal F$ of at most $n$ subsets of $\{ 1, 2, \dots, n \}$.
The union closure $\mathcal F$ is another set family $\mathcal C$ containing every set that can be constructed by taking the union of 1 or more sets in $\mathcal F$.
By $|\mathcal C|$ we denote the number of sets in $\mathcal C$.

What is the fastest way to compute the union closure?

I have showed a equivalence between the union closure and listing all maximal independent sets in a bipartite graph, therefore we know that deciding the size of the union closure is #P-complete.

However there is a way to list all maximal independent sets (or maximal cliques) in $O(|\mathcal C| \cdot nm)$ time for a graph with $n$ nodes and $m$ edges Tsukiyama et al. 1977.
But this is not specialized for bipartite graphs.

We gave an algorithm for bipartite graphs with runtime $|\mathcal C| \cdot \log |\mathcal C| \cdot n^2$ <http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf>

Our method is based on the observation that any element in $C$ can be made by the union of some other element of $C$ and one of the original sets.
Hence we will whenever we add an element to $C$ try to expand it by one of the $n$ original sets.
For each of these $n \cdot |C|$ sets we need to check if they are still in $C$. We store $C$ as a binary search tree, so each lookup takes $\log |C| \cdot n$ time.

Is it possible to find the union closure $\mathcal C$ in $O(|\mathcal C| \cdot n^2)$ time?
Or even in time $O(|\mathcal C| \cdot n)$?

**Tags:** co.combinatorics, graph-algorithms, clique, independence
> **Comments:**
> **username_1**: In the equivalence that you've shown between union closure and maximal ind. sets in bipartite graphs, is the equivalence a bijection? Or in other words, in your algorithm for listing all miximal ind. sets of a bipartite graph, is $|C|$ the number of maximal ind. sets?  
> **username_0**: Yes  it is a bijection so $|C|$ is the number of maximal independent sets. (note that the emptyset must be defined to be in $C$).  
> **username_2**: While this is unlikely to help with your question, what you're asking is a special case of computing the upward closure of elements in a lattice, and I wonder if there are results from there that might be useful.  
> **username_3**: The survey I point to in my answer below gives some links with lattices.  

---

## 1 answers

### Answer by username_3 on 2012-11-13. Score: 3 | Accepted answer

The complexity of enumerating maximal independent sets in graphs is the same as in bipartite graphs, so bipartiteness does not bring anything new.

You have an algorithm (with exponential space) in $O(|C|\cdot n^2)$, but no polynomial space algorithm that acheives this time complexity is known. The following paper <http://www.sciencedirect.com/science/article/pii/S0166218X08004563> is a good survey.


---

