Reduce size of set of sets through unions, restricted by maximum union size

user_593146 0
Viewed 125

I have a set of distinct sets, where none of the distinct sets have more than k elements. E.g. with k of 4:

set([frozenset({0, 3, 6}),
     frozenset({0, 1, 2}),
     frozenset({6, 7}),
     frozenset({8, 7}),
     frozenset({1, 2}),
     frozenset({9, 11, 6, 7}),
     frozenset({0, 11, 6, 7}),
     frozenset({9, 6, 7}),
     frozenset({11, 6, 7}),
     frozenset({0, 6, 7}),
     frozenset({0, 6}),
     frozenset({0, 3, 6, 7}),
     frozenset({11}),
     frozenset({8}),
     frozenset({8, 6, 7}),
     frozenset({0, 1, 3, 6}),
     frozenset({0, 1, 6}),
     frozenset({0, 1}),
     frozenset({3, 4, 5}),
     frozenset({9, 6}),
     frozenset({9, 10}),
     frozenset({4, 5}),
     frozenset({11, 9, 3, 6}),
     frozenset({9, 11, 6}),
     frozenset({9, 3, 6}),
     frozenset({3, 6}),
     frozenset({0, 9, 3, 6}),
     frozenset({10}),
     frozenset({9, 10, 6}),
     frozenset({0, 3, 4, 6}),
     frozenset({3, 4, 6}),
     frozenset({3, 4}),
     frozenset({11, 6})])

I want to unite the frozen sets with each other to make the amount of entries in the surrounding set as small as possible. However, the aforementioned condition that no set may have a size greater than k must remain true. If I were to brute force this, this would be doable in O(n³) time (oof) in O(n!) time (oooof). Depending on the order in which one matches possible unions one can create states where the correct solution can no longer be reached.

E.g.: If given {1, 3}, {1, 2}, {3, 4}, {3, 5} with a limit of 3 elements per set I were to unite {1, 3} and {3, 4} this would yield {1, 3, 4}, {1, 2}, {3, 5}. Had I instead united {3, 4} and {3, 5}, I would have gotten {1, 3}, {1, 2}, {3, 4, 5} and then {1, 2, 3}, {3, 4, 5} (one set less).

I see no obvious strategy here. In the example, all 4 initially available sets have the same size and except for {1, 2} and {3, 4} they all share exactly one element between each other. So: how do I reduce the size of a set of sets through unions of the inner sets as much as possible, while having the inner sets not exceed a given size?

EDIT 1: I was able to write a function which eliminates subsets in O(n²), which is a good start.

def uniteSetsWithSupersets(s: set) -> set:
    t = set()
    for k in s:
        for l in t:
            if k.issubset(l) or l.issubset(k):
                t.remove(l)
                t.add(k.union(l))
                break
        else:
            t.add(k)
    return t
set algorithm python
1 Answers

I would be surprised if this had a simple solution. So here is an outline of a pragmatic approach that could work depeding on the size of your inputs.

Start with a slight modification. Say that we are looking for a smallest "cover" collection of sets c_1, ..., c_n (each of size <= k) such that every given set s_i is a subset of one or more cover sets.

Find all the candidates to be in the cover. For that take repeated unions of given sets s_i with each other and save all possible results of cardinality less than k.

Then formulate a constraint programming problem. Assign an indicator variable to each of the candidates. For each s_i add a constraint, specifying that the sum of the variables corresponding to candidates containing it add to more than 1. Add a minimisation target over the sum of the indicator variables. Solve. ortools can handle this (https://google.github.io/or-tools/python/ortools/sat/python/cp_model.html)

Finally modify the solution, and remove some unnecessary elements from the cover sets (if there are any).

user_61101600
Related