# algorithms – Minimal number of unions of sets such that no union has more than N elements

I have some sets, and can combine them by taking their union. I can take unions of the unions, too. I want to take unions until the total number of sets is as small as possible, with one caveat: that none of the unions can have more than $$N$$ elements. (So that the problem always has a solution, none of the input sets will ever have more than $$N$$ elements.)

If the input to the problem is a set of sets $${S_1 … S_n}$$, the result should be disjoint partitioning of the input into subsets, such that the size of the union of the sets in each subset is always smaller than $$N$$, which might look something like $$left{left{S_1,S_3right},left{S_2,S_4,S_5right},…right}$$.

What’s the best algorithm to do that? The brute force algorithm is exponential, and naively memoizing it is GL-complete (because so is the bipartite graph isomorphism problem). This question is similar in spirit, but it’s about finding one set, instead of the smallest set of sets.

Posted on