When testing n items, how to cover all t-subsets by as few s-subsets as possible?

Question

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?

Answer 1

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.

Answer 2

Form the undirected graph $G$ where each vertex is a pair of items, and where there is an edge between two vertices if they share an item in common. In other words, $G=(V,E)$ where $V=\{\{a,b\} : a,b \in \text{Items} \land a\ne b\}$ and $E=\{(s,t) : s,t \in V \land |s\cap t|=1\}$. The graph has ${n \choose 2}$ vertices, and every vertex has $2n-4$ edges incident on it.

Then one approach would be to find a maximum matching in $G$. Edmonds' algorithm can be used to find such a maximum matching in polynomial time. If you're lucky, this will give you a perfect matching, and then you're good. Each edge $(\{A,B\},\{B,C\}) \in E$ in the matching corresponds to a test case $A B C$. Since every vertex is incident with one edge in the perfect matching, you have covered all pairs, using ${n \choose 2}/2$ test cases, which is within a $1.5$ factor of optimal. If you don't get a perfect matching, add a few more test cases as needed to achieve full coverage.

Answer 3

In the case of $s=3$ and $t=2$ you need to perform at least ${n \choose 2}/3$ tests, since there are ${n \choose 2}$ pairs and every test covers 3 pairs. That means that you can do the trivial thing and perform ${n \choose 2}$ tests, and be only a factor of 3 worse than the optimum.

If you are actually programming this, then a way to optimize this could be by first picking some number tests at random, and then do the brute force on the pairs not covered by the test so far.

---

For general $s$ and $t$, there is a lower bound of ${n \choose t}/{s \choose t}$ tests. For an upper bound I'm claiming that is is enough to make $C \cdot \frac{{n \choose t}}{s \choose t}\cdot {\log({n \choose t})} \leq O(t \cdot (\frac{n-t}{s-t})^t \log(n))$ tests.

Let's see what happens we we choose the tests uniformly at random.If you pick an $s$-tuple $S \subseteq [n]$ at random, then for a fixed $t$-tuple $X \subseteq [n]$, we have $\Pr[X \subset S] = \frac{{n-t \choose s-t}}{{n \choose s}}$. Therefore, if we pick $C \cdot {n \choose t} \cdot {\log({n \choose t})}$ tests at random, then $$\Pr[X \text{ does not belong to any of them}] = \left(1 - \frac{{n-t \choose s-t}}{{n \choose s}}\right)^{C \cdot {n \choose t} \cdot {\log({n \choose t})}} \leq \exp \left(-C \frac{{n-t \choose s-t}{n \choose t}}{{n \choose s}{s \choose t}} \cdot \log({n \choose t})\right) = \exp(-C \log{n \choose t})\leq 1/{n \choose t}.$$

Therefore, by the union bound, after $O(t \cdot (\frac{n-t}{s-t})^t \log(n))$ random tests all $t$-tuples will be covered.