Covering Array on the Cartesian Product of Hypergraphs

Abstract

Covering array (CA) on a hypergraph H is a combinatorial object used in interaction testing of a complex system modeled as H. Given a t-uniform hypergraph H and positive integer s, it is an array with a column for each vertex having entries from a finite set of cardinality s, such as $\mathbb {Z}_s$, and the property that any set of t columns that correspond to vertices in a hyperedge covers all $s^t$ ordered t-tuples from $\mathbb {Z}_s^t$ at least once as a row. Minimizing the number of rows (size) of CA is important in industrial applications. Given a hypergraph H, a CA on H with the minimum size is called optimal. Determining the minimum size of CA on a hypergraph is NP-hard. We focus on constructions that make optimal covering arrays on large hypergraphs from smaller ones and discuss the construction method for optimal CA on the Cartesian product of a Cayley hypergraph with different families of hypergraphs. For a prime power $q>2$, we present a polynomial-time approximation algorithm with approximation ratio $\left( \Big \lceil \log _q\left( \frac{|V|}{3^{k-1}}\right) \Big \rceil \right) ^2$ for constructing covering array CA(n, H, q) on 3-uniform hypergraph $H=(V,E)$ with $k>1$ prime factors with respect to the Cartesian product.