# 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_3\right\},\left\{S_2,S_4,S_5\right\},...\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.

• Assume that your sets are disjoint. Then it becomes a bin packing problem, which is strongly NP-hard.
– user114966
Apr 5, 2021 at 6:03