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.

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.

February 2004 July 2004 August 2004 September 2004 October 2004 November 2004 December 2004 January 2005 February 2005 March 2005 April 2005 May 2005 June 2005 July 2005 August 2005 September 2005 October 2005 November 2005 December 2005 January 2006 February 2006 March 2006 April 2006 May 2006 June 2006 July 2006 August 2006 September 2006 October 2006 November 2006 January 2007 April 2007 May 2007 June 2007 November 2007 December 2007 January 2008 March 2008 June 2008 February 2009 June 2009 February 2010 November 2010