On Minimizing a Set of Tests
Bernard M. E. Moret, Henry D. Shapiro · SIAM Journal on Scientific and Statistical Computing · 1985
Minimizing the size or cost of a set of tests without losing any discrimination power is a common problem in fault testing and diagnosis, pattern recognition, and biological identification. This problem, referred to as the minimum test set problem, is known to be NP-hard, so that determining an optimal solution is not always computationally feasible. Accordingly, researchers have proposed a number of heuristics for building approximate solutions, without, however, providing an analysis of their performance. In this paper, we take an in-depth look at the main heuristics and at the optimal solution methods, both from a theoretical and an experimental standpoint. We characterize the worst-case behavior of the heuristics and discuss their use in bounding. We then present the results of extensive experimentation with randomly generated problems. While the exponential explosion suggested by the problem’s NP-hardness is apparent, our results suggest that real world testing problems of large sizes can be solved quickly at the expense of large storage requirements.