Covering arrays avoiding forbidden edges

Covering arrays (CAs) can be used to detect the existence of faulty pairwise interactions between parameters or components in a software system. The generalization considered here applies to the situation in which some input combinations are invalid, a requirement quite common in software testing. In this paper, we study covering arrays avoiding forbidden edges (CAFEs), where certain pairwise interactions are forbidden while all others must be covered, and we aim to minimize the number of tests. We establish a theoretical framework for this problem, by providing connections to the edge clique covering problem, lower and upper bounds, complexity results and a recursive construction. We also give an algorithm for the case of binary alphabets.