# An algorithm that finds a minimal partition of the set $S$

I have a number of sets $S_1,...,S_n$ and their union $S = \bigcup_{i\in [1,n]}{S_i}$.
I need an algorithm that finds a minimal partition of the set $S$ in non-intersecting subsets $\hat{S}_1,...,\hat{S}_k$ such that every set $S_i$ can be represented as $S_i = \hat{S}_{j_1}\cup ... \cup \hat{S}_{j_r}$.
Assume that all basic set operations are constant time.

My guess is that the algorithm will be exponential time where the input is $n$. Because all pairs intersection of $n$ input sets is not enough to find the minimal partition. We should also do all $3, 4,...,n$ intersections, because of situations like on the picture above.

Another question is, how the algorithm will improve, if we somehow prove that the multiset of all-pair intersections and remainings of these intersections have a subset of non-intersecting sets that cover $S$ ?

• Shouldn't this algorithm be $\operatorname{NP}$-complete? At least intuitively (i.e. without having thought about it) it seems like you should be able to reduce the Independent set problem to this question in polynomial time. Commented Aug 23, 2017 at 8:53
• Oh, and I should say that in my comment above I assumed $S$ to be a finite set - basically a natural number coding a finite subset of $\mathbb N$. Commented Aug 23, 2017 at 8:59
• Have you tried my idea or figured something else? Just wonder what solution this problem has. Commented Sep 4, 2017 at 8:13

THIS IS NOT AN ANSWER, just an idea that I do not know currently how to prove.

Take one-element sets and merge together all the one-element sets that have identical set of supersets $S_i$ (i.e. they form a subset of some of the sets).

Now, I do not know how to prove it or whether it is even really correct, but to reduce the number of sets requires to merge some of these merged sets $\hat S_j$ together. But that is not possible, since I think it causes some of the sets being unobtainable afterwards.

Since if there is a set having $\hat S_1$ as a subset, but has something not from $\hat S_2$ as an element, by merging these two you remove a necessary subset for generating this set. And since you are looking for disjoint sets, you cant very well copy those elements from $\hat S_1$ in another generating sets. Nor can you divide the set to redistribute parts into other sets, becuase these parts have the exact same set of supersets.

But I do not have a proof, therefore I am posting this just as a possible inspiration and not an answer, because I could not put it all into comment.