Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Say we have a collections of sets $\mathcal X = \{X_1, \dots, X_n\}$ (not necessarily disjoint), and we want to count the number of possible unions of sets in $\mathcal X$, i.e. the size of $\{\bigcup_{Y \in \mathcal Y} Y \,|\, \mathcal Y \subseteq \mathcal X \}$.
Is there a name for this problem? What are the fastest algorithms to solve this problem?
I found the answer here. It is called the union closure and the complexity appears to be the same as computing the number of maximal independent sets in a bipartite graph.
