Finding the Best CAFE Is NP-Hard

In this paper, we look at covering arrays with forbidden edges (CAFEs), which are used in testing applications (software, networks, circuits, drug interaction, material mixtures, etc.) where certain combinations of parameter values are forbidden. Covering arrays are classical objects used in these applications, but the situation of dealing with forbidden configurations is much less studied. Danziger et. al. [8] have recently studied this problem and shown some computational complexity results, but left some important open questions. Around the same time, Martinez et al. [18] defined and studied error-locating arrays (ELAs), which are very related to CAFEs, leaving similar computational complexity questions. In particular, these papers showed polynomial-time solvability of the existence of CAFEs and ELAs for binary alphabets (g = 2), and the NP-hardness of these problems for g >= 5. This not only left open the complexity of determining optimum CAFEs and ELAs for g = 2, 3, 4, but some suspicion that the binary case might be solved by a polynomial-time algorithm. In this paper, WC prove that optimizing CAFEs and ELAs is indeed NP-hard even when restricted to the case of binary alphabets. We also provide a hardness of approximation result. The proof strategy uses a reduction from edge clique covers of graphs (ECCs) and covers all cases of g. We also explore important relationships between ECCs and CAFEs and give some new bounds for uniform ECCs and CAFEs.