Given an array of array: S = {s1, s2, ... , sn}, where si = {i1, i2, ..., im} and every element in array si is the integer from 1 to n with m ≤ n/2. For example, S = {{1, 2, 3}, {1, 3, 4}, {2, 5, 6}, {4, 5, 6}}, where m = 3 and n = 6.
If for any element si, sj in S they are disjoint with |si| + |sj| ≤ n, we say si and sj are in the same group g.
Question: For a given array S, I wonder if there is an efficient algorithm to output the group with minimal count. Still the example mentioned previously:
INPUT: S = {{1, 2, 3}, {1, 3, 4}, {2, 5, 6}, {4, 5, 6}}
OUTPUT:G1 = {{1, 2, 3}, {4, 5, 6}}, G2 = {{1, 3, 4}, {2, 5, 6}}, GroupCount = 2
The only method I can figure out is BF, I hope anyone can give an answer to this question or give some materials about this.