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