2
$\begingroup$

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.

enter image description here

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented Aug 23, 2017 at 8:53
  • $\begingroup$ 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$. $\endgroup$ Commented Aug 23, 2017 at 8:59
  • $\begingroup$ Have you tried my idea or figured something else? Just wonder what solution this problem has. $\endgroup$
    – TStancek
    Commented Sep 4, 2017 at 8:13

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .