wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Finding if a set of subsets contains a partition
        
(Message started by: dudiobugtron on Jun 5^th, 2014, 7:32pm)

Title: Finding if a set of subsets contains a partition
Post by dudiobugtron on Jun 5^th, 2014, 7:32pm

Hi! (Apologies if this is not the right place to post this, as it's a straight CS question and not a riddle I know the answer to. It's not homework, and is just for my personal interest.)

Here is the problem:
-----------------------

I have a set N = {1,2,3,...,n}. I also have a set S of subsets of N. (So S is a subset of the powerset of N). I want to know if there is some subset P of S where the elements of P form a partition of N. (ie: each element of N is in exactly 1 element of P.)

eg: N = {1,2,3,4,5}
S = [1},{1,2},{2,3},{3,5},{1,4},{2,4},{1,4,5]
P = [2,3},{1,4,5] is a partition of N.

Does anyone have a good algorithm for determining this? Is this a known problem? Is it P? NP complete? etc...

Title: Re: Finding if a set of subsets contains a partiti
Post by Grimbal on Jun 6^th, 2014, 4:42pm

The number of subsets of the powerset of N is exponential in N. So could be S.
But maybe there is a solution that is polynomial in the size of S.

Title: Re: Finding if a set of subsets contains a partiti
Post by dudiobugtron on Jun 6^th, 2014, 6:48pm

on 06/06/14 at 16:42:12, Grimbal wrote:

The number of subsets of the powerset of N is exponential in N. So could be S.
But maybe there is a solution that is polynomial in the size of S.

So does that mean there is certainly not a general solution that is polynomial in N? If so, that is really useful to know. :)

Title: Re: Finding if a set of subsets contains a partiti
Post by towr on Jun 7^th, 2014, 4:25am

Suppose S is the set of all subsets of N that contain 1. There is no way to find that out except by looking at all of S, the size of which is exponential in N (it's 2^N-1). So no, there is not a general solution that is polynomial in N.

Unless, perhaps you get some index to S (i.e. information that let's you skip (to) parts of input without having to process it). But even then I'm doubtful.

Title: Re: Finding if a set of subsets contains a partiti
Post by dudiobugtron on Jun 9^th, 2014, 12:41pm

OK, that makes a lot of sense, thanks!

So I need to restrict myself to subsets S that are themselves polynomial in N, and then find a solution which is polynomial in S.

------------------------------
PS: I think it is cool that adding more items to the subset actually makes it harder to tell if it contains a partition. Naively, you might think that since adding more elements makes it more likely to contain a partition, that it would be easier to tell if it did. But I guess a better way to think about it is that it's harder to tell that it doesn't.