Hardness results for covering arrays avoiding forbidden edges and error-locating arrays

Covering arrays avoiding forbidden edges (CAFEs) are used in testing applications (software, networks, circuits, drug interaction, material mixtures, etc.) where certain combinations of parameter values are forbidden. Danziger et al. (2009) [8] have studied this problem and shown some computational complexity results. Around the same time, Martinez et al. (2009) [19] defined and studied error-locating arrays (ELAs), which are closely related to CAFEs. Both papers left some 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. In this paper, we prove that optimizing CAFEs and ELAs is indeed NP-hard even when restricted to the case of binary alphabets, using a reduction from edge clique covers of graphs (ECCs). We also provide a hardness of approximation result. We explore important relationships between ECCs and CAFEs and give some new bounds for uniform ECCs and CAFEs.