Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!uwm.edu!ogicse!orstcs!
From: almualh@darwin.cs.orst.edu (Hussein Almuallim)
Newsgroups: comp.theory
Subject: Minimum Set Cover Problem
Message-ID: <1991May30.072410.15187@lynx.CS.ORST.EDU>
Date: 30 May 91 07:24:10 GMT
Sender: @lynx.CS.ORST.EDU
Organization: Computer Science Department, Oregon State Univ.
Lines: 28
Originator: almualh@darwin.CS.ORST.EDU
Nntp-Posting-Host: darwin.cs.orst.edu


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.