Covering array on the Cartesian product of hypergraphs (Q6581902)

A covering array is a mathematical object used in designing the experiment for combinatorial testing. In industrial applications, the columns of the covering array denote factors of the system and every row points a test to be performed. As the cost of the testing is proportional to the size of the covering array, the cost-optimization and hence minimizing the size of a covering array is pertinent in an application environment. It is known that finding an optimal covering array on a hypergraph is NP-hard. The authors here mainly focus on the covering array on the Cartesian product of Cayley hypergraphs and successfully endeavored to build an optimal covering array on a large hypergraph by taking clues from the product of smaller hypergraphs. They nicely obtain a polynomial-time approximation algorithm for constructing a covering array on a 3-uniform hypergraph of bounded degree, with \(k>1\) prime factors with respect to the Cartesian product of hypergraphs. They also indicate directions for further research.