Friday, September 24, 2004

solution to set theory question

Marvel at Richard Karp's creativity.....

The black box algorithm finds one set of subsets among the given set of subsets so that their union gives the main set and they are pairwise disjoint. Now, somehow we need to make sure that it returns a set of subsets whose size is K.

The solution is to add K new distinct elements to the main set (change the main set). Say the new elements are X1, X2, X3.....Xk. Add X1 to all the given M subsets and get new subsets. Add X2 to all the subsets and get another set of new subsets, and so get M*K new subsets. Now feed the changed main set and the new set of M*K subsets to the blackbox algorithm (just once).

You can verify this solution quite easily.

No comments: