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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.