[comp.theory] Generating subsets which are not supersets

bdm659@csc.anu.edu.au (05/18/91)

Let S = {1,2,...,n}, and suppose that X[1],...,X[k] are subsets of S.

I wish to generate all the subsets of S which are not supersets of
any X[i].  In a typical application, n will be about 20, k will be
100-1000 and the X[i] will have size 3-5.

Does anyone know how this can be done fast?  Practical performance
is more important than theoretical nicety.    Thanks.

Brendan McKay.   Australian National University.

bimandre@icarus.cs.kuleuven.ac.be (Andre Marien) (05/23/91)

In article <1991May18.120016.1@csc.anu.edu.au> bdm659@csc.anu.edu.au writes:
>Let S = {1,2,...,n}, and suppose that X[1],...,X[k] are subsets of S.
>
>I wish to generate all the subsets of S which are not supersets of
>any X[i].  In a typical application, n will be about 20, k will be
>100-1000 and the X[i] will have size 3-5.
>
>Does anyone know how this can be done fast?  Practical performance
>is more important than theoretical nicety.    Thanks.

reformulation:

X[1] = { a1,   a2,      , am1 }
becomes:
C[1] = ~p1  v ~p1  v ... v ~p1
          1      2            m1

The problem becomes:
find all models M for C[1],...,C[k]

So, there is a lot of literature on this problem, but no always efficient algorithm.

Andre' Marien
bimandre@cs.kuleuven.ac.be