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 Zs, and the property that any set of t columns that correspond to vertices in a hyperedge covers all st ordered t-tuples from Zst 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 (⌈logq⁡(|V|3k−1)⌉)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