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