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.pdfOur 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)$?
Computing the union closure
co.combinatorics;graph algorithms;clique;independence
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. 