Algorithm question: minimal sets?

Jonathan Epstein Jonathan_Epstein at nih.gov
Tue Sep 18 11:04:13 EST 2001

I just sent composed a long response to this which may have been lost due to
operator error

Here's a summary: I believe that this problem is known as the Set Cover
Decision Problem, and is NP-Hard, i.e., it requires exponential time.

Here are some resources:




"Charlie" <cckim at stanford.edu> wrote in message
news:Pine.GSO.4.31.0109131835160.232-100000 at saga12.Stanford.EDU...
> I have an algorithmic problem that I suspect has already been solved long
> ago, but, alas, I am a biologist.
> And so:
> I have a large number of sets of data, which includes many members each.
> I would like to known the smallest possible union of these sets of data
> that would include every member.
> An example:
> D1 = (A, B, C, D) (dataset 1 contains members A, B, C)
> D2 = (A, B, D)
> D3 = (C, D, E)
> D4 = (Z)
> The smallest set of data which would include all members would be D1, D3,
> and D4.
> Does anyone know an algorithm that does this?
> Thanks in advance,
> Charlie

More information about the Bio-soft mailing list

Send comments to us at biosci-help [At] net.bio.net