algorithm - Given N sets of elements, find minimal union of M sets

Question

Given a recipe as a set of ingredients, I am trying to find minimum ingredients that make a week worth of meals. This translates to the above problem, with N as number of recipes and M =7.

eg. if the initial sets are [{1,2}, {2,3}, {1,2,3}, {1}, {2}], and M=3
The minimal union is {1,2}.

I am looking for high level approaches to solve this. I feel this can be reduced to a BFS, but I want to see if other approaches could also make it optimal.

Note: There might be multiple such sets, with same cardinality.

Answer 1

This problem is known as MINIMUM k-UNION, and it is NP-hard, as shown here:

• Staal A. Vinterbo (2002). A Note on the Hardness of the k-Ambiguity Problem. DSG Technical Report 2002-006.

So no-one knows any algorithm to solve it that runs in time that's polynomial in the size of the input.

In your case, you would probably be happy to accept an approximate solution: that is, a collection of recipes with a small union of ingredients, but not necessarily the very smallest such collection. So I suggest that you try the greedy algorithm: iteratively build up a collection of recipes by adding at each stage the recipe that minimizes the size of the union. Here's a na?ve implementation in Python:

def small_union(sets, k):
    """
    Choose `k` elements from `sets` and return their union.  Attempt
    to return a fairly small union using a greedy approach.

    >>> small_union([{1,2}, {2,3}, {1,2,3}, {1}, {2}], 3)
    set([1, 2])
    >>> small_union([{1,2}, {2,3}, {3,4}, {1,4}], 3)
    set([1, 2, 3, 4])
    """
    union = set()
    for _ in xrange(k):
        s = min(sets, key = lambda s: len(s | union))
        sets.remove(s)
        union |= s
    return union