HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Count all possible unions in a collection of sets

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
allcollectionpossibleunionscountsets

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#33571, answer score: 4

Revisions (0)

No revisions yet.