2003-14: Tight Approximability Results for Test Set Problems in Bioinformatics

DIMACS TR: 2003-14

Tight Approximability Results for Test Set Problems in Bioinformatics

Authors: Piotr Berman and Bhaskar DasGupta and Ming-Yang Kao

ABSTRACT
In this paper, we investigate several versions of a test set problem. In the simplest version, given a family of tests, viewed as subsets of the universe, we want to select the smallest subfamily that separates every two elements of the universe. We show that this problem is exactly as difficult to approximate as the set cover problem, up to a factor of 1 plus or minus o(1). The same holds for several more elaborate versions of the problem that have applications in bioinformatics; for example, in one version the universe consists of strings over a finite alphabet and each test checks the presence of a specific substring. We also show that if we allow to form tests as unions of the given tests, the problem has essentially the same level of computational intractability as graph coloring.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-14.ps.gz

DIMACS Home Page