Covering arrays avoiding forbidden edges and edge clique covers

Abstract

Covering arrays avoiding forbidden edges (CAFEs) are combinatorial designs which can be used to generate test suites for practical testing applications. CAFEs generate test suites in which all required pairwise interactions between any two factors are tested at least once each, with the property that a specified list of pairwise interactions, the so called forbidden interactions, are avoided by all tests generated by the CAFE. Consequently, CAFEs can be applied to testing applications wherein constraints are imposed on the factors of the tests, resulting in forbidden interactions. In this thesis, we study CAFEs, as well as their relationship to the edge clique cover problem from graph theory. We give new results and bounds for uniform edge clique covers and CAFEs. We establish the computational complexity of several problems related to CAFEs and edge clique covers. In particular, we prove that finding an optimal CAFE (as well as finding an optimal error-locating array) for a graph is NP-hard, even for the case of binary alphabets.