Re: easy combinatorial algorithm, or not??


I forgot to mention that I'm currently thinking "NO" to the question I
just posted. The reason is that you need 1 bit of information to answer
the question "does element X exist in set S"? In the context of the
problem I mentioned, that gives you a factorial space number of bits to
start with.


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.

.