Problem Detail: This problem arose from software testing. The problem is a bit difficult to explain. I will first give an example, then try to generalize the problem. There are 10 items to be tested, say A to J, and a testing tool that can test 3 items at the same time. Order of items in the testing tool does not matter. Of course, for exhaustive testing, we need $^{10}C_{3}$ combinations of items. The problem is more complex. There is an additional condition that once a pair of items has been tested together, than the same pair does not need to be tested again. For example, once we executed the following three tests: A B C A D E B D F we do not have to execute: A B D because the pair A,B was covered by the first test case, A,D was covered by the second, and B,D was covered by the third. So the problem is, what is the minimum number of test cases that we need to ensure that all pairs are tested? To generalize, if we have n items, s can be tested at the same time, and we need to ensure that all possible t tuples are tested (such that s > t), what is the minimum number of test cases that we need in terms of n, s and t? And finally, what would be a good algorithm to generate the required test cases?
Asked By : wookie919
Answered By : Peter Shor
The block designs you want (for testing 3 things at a time, and covering all pairs) are called Steiner triple systems. There exists a Steiner triple system with $frac{1}{3} {n choose 2}$ triples whenever $n equiv 1 mathrm{ or } 3$ mod $6$, and algorithms are known to construct these. See, for example, this MathOverflow question (with a link to working Sage code!). For other $n$, you could round up to the next $n’ equiv 1 mathrm{ or } 3$ mod $6$, and use a modification of this triple system for $n’$ to cover all pairs for $n$. If you want the best construction for other $n$, the number of triples required is the covering number $C(n,3,2)$, and is given by this entry in the on-line encyclopedia of integer sequences. This links to the La Jolla Covering Repository which has a repository of good coverings. The online encyclopedia of integer sequences gives a conjectured formula for $C(n,3,2)$; if this formula holds, intuitively that means there should probably be good algorithmic ways of constructing these coverings, but since the formula is conjectured, it is clear that nobody currently knows them. For high covering numbers, good coverings are harder to find than for $C(n,3,2)$, and the repository will give better solutions than any known efficient algorithms.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13788 Ask a Question Download Related Notes/Documents
