Re: easy combinatorial algorithm, or not??

Thanks for the quick reply. You're right about the multiset, it should
have said just a regular set (of alpha-sets).

The thing is that storing R explicitly is factorial space, even with
bit vectors and such. Given R explicitly, it's relatively easy to
calculate without enumeration for any given T if all it's alpha-subsets
are in R. The problem, from a complexity point of view, is as follows:

R is initially the empty set. Therefore any T will test "no", i.e. it's
alpha-subsets are not contained in R. However, for every "no" test, the
alpha-subsets of T are to be added to R. And therein lies the problem!
Can we add all subsets to R without explicitly doing so, for the
purpose of the yes/no decision?

Any ideas?

Thanks again!
-Mayank


Ben Bacarisse wrote:
Mayank <mayanklahiri@xxxxxxxxx> wrote:
Hi all,

I'm stumped on finding an polytime algorithm for the following
seemingly easy subset problem. Does anyone have any information on this
problem
(identification/complexity/reduction/efficient solution, etc)?

Ideally, I'd like a polytime algorithm for this, or some concrete
indication that it's NP.

Given:
1) a set of sorted positive integers S = {s_1, ..., s_t} without
repetition.
2) a integer constant alpha, 1 <= alpha <= |S|
3) a multiset R of different (possibly all) alpha-subsets of S

I am assuming you don't mean a multiset here (or if you do, it means
something else to you). To me, a multiset is a set that "allows
duplicates". If you do mean that sort of multiset, I don't understand
your problem.

Problem:
Given an arbitrary subset T of S s.t. |T| >= alpha, are all of T's
alpha-subsets contained in R?

Ideally, this would be done without enumeration of all of T's
alpha-subsets and without explicitly storing R, as that pushes us into
factorial time.

I am not sure what you mean by "without storing R". R is part of the
problem input so it must be represented somehow. How you do so will
affect the complexity.

One solution (unless I have the wrong end of the stick) is to form R'
consisting of those elements of R that contain elements in S - T. If

|R| - |R'| = combinations(alpha, |T|)

your answer is "yes" (otherwise "no"). Of course, you don't have to
"store" R' -- you just need to count the number of elements of R that
contain only elements in T. Complexity left as an exercise ;)

--
Ben.

.