Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.