Suppose there are m(m<100) sets and elements are limited to 1-n(n<100). I am looking for an algorithm to find a combination of sets that cover the most elements and any two sets have no intersection.

Example:

Input: [{1,2,3},{2,4},{3,5}]

Output: [{2,4},{3,5}]

If there is a solution better than O(2^m)?

CodePudding user response：

Let me restate the problem as I understand it.

You have a collection of sets. You'd like to find a subcollection where no two sets intersect, whose union is as big as possible.

This optimization problem is an NP-hard problem, and therefore every known algorithm is exponential in m. This can be seen by restricting to the special case where every set has 3 elements. That is the 3-dimensional matching problem. The decision variant is, "Find whether you can cover at least k elements." The decision variant was on Karp's original list of 21 NP-complete problems.

Why is the optimization version NP-hard and decision version NP-complete? That is because there is no easy way to verify that a claimed optimal set of subsets is in fact optimal. But it is easy to verify that a collection of disjoint subsets that covers at least k elements is what you claim.