0
244views
Test Suite Minimization Problem
Given: A test suite TS; a set of test case requirements $r_{1}, r_{2}, \ldots, r_{n}$ that must be satisfied to provide the desired testing coverage of the program; and subsets of $\mathrm{TS}, T_{1}, T_{2}, \ldots, T_{n}$ one associated with each of the $r_{i}'s$ such that any one of the test cases $t_{j}$ belonging to $T_{i}$ can be used to test $r_{i}$
Problem: Find a representative set of test cases from $T S$ that satisfies all the $r_{i}'s$.
The $r_{i}'s$ can represent either all the test case requirements of a program or those requirements related to program modifications. A representative set of test cases that satisfies the $r_{i}'s$ must contain at least one test case from each $T_{r}$ Such a set is called a hitting set of the group of sets, $T_1, T_{2}, \ldots, T_{n}.$ Maximum reduction is achieved by finding the smallest representative of test cases. However, this subset of the test suite is the minimum cardinality hitting set of the $T_{i}^{\prime} s$ and the problem of finding the minimum cardinality hitting set is NP complete. Thus, minimization techniques resort to heuristics.