almualh@darwin.cs.orst.edu (Hussein Almuallim) (05/30/91)
Friends:
Can anyone suggest references/ideas for the following question related
to the Minimum Set Cover Problem. First, let me pose the MSC problem as
follows:
Given: a set of m elements
a cover of size n
an integer p
Question: Does there exist any sub-cover of the m elements
of size <= p ??
A direct way to deal with this is to try all the (n choose p) p-subsets.
This, however, will result in O(n^p) or O(2^n) time complexity.
On the other hand, since this is an NP-complete problem,
we know that (unless P=NP) there exists no algorithm to solve this
in time polynomial in n, m and p (or in n and m alone since p is
bounded by n).
Now, my question is: Is there anything known about whether there
exists an algorithm to solve this problem in time polynomial in n, m
and 2^p (two to the power p) ? That is, we don't mind that p appears
in the exponent as long as the base is some constant.
Thank you for your help.
Hussein.