10
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Nov 11, 2012 at 16:27
  • $\begingroup$ 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$). $\endgroup$ Nov 11, 2012 at 16:33
  • $\begingroup$ 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. $\endgroup$ Nov 11, 2012 at 18:08
  • $\begingroup$ The survey I point to in my answer below gives some links with lattices. $\endgroup$
    – M. kanté
    Nov 13, 2012 at 8:48

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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