# Computing the union closure

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)$?

-
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 Nov 11 '12 at 16:27
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 Nov 11 '12 at 16:33
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 Nov 11 '12 at 18:08
The survey I point to in my answer below gives some links with lattices. – M. kanté Nov 13 '12 at 8:48

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.