Tayzwi

A main set S and a good number of its subsets A1, A2......Am (m subsets) are given (the total number of subsets is exponential; not all of them are given, but a lot of them (m) are given).

There exists a blackbox algorithm that can take the main set S and the given 'm' subsets and return one combination of disjoint subsets (all pair-wise intersections are null), and whose union gives the main set S.

Say the main set is {1, 2, 3, 4, 5, 6, 7, 8, 9} and the 9 subsets given are
{1, 2, 3}{4, 5, 6}{7, 8, 9}
{1, 2, 3, 4, 5} {6, 7, 8, 9}
{1, 2, 3, 4}{5, 6, 7} {8}{9}

Now we see that the black-box algorithm could return the first row of subsets ({1, 2, 3}{4, 5, 6}{7, 8, 9}) as the answer, the second row as the answer, or the third row as the answer. This is because all these three solutions satisfy the constraint: The returned answer should contain a combination so that they are pairwise disjoint and whose union gives the main set S.

Now, the problem is to somehow use this blackbox algorithm to return the combination of size K. From the above example, if K = 3, the first row should be returned, if K = 4, the last row should be returned.

So, the input to the problem is a set S, a few of its subsets, and a constant K. The output should be K of these subsets so that they are all mutually disjoint and whose union gives S. This problem can use the blackbox algorithm that gives any such solution (the black box doesnt have a clue of K). No combinatorial exhaustive searches allowed.

From my algorithms and complexity course.