Mixed Covering Arrays on Hypergraphs

Abstract

Mixed covering arrays are natural generalizations of covering arrays that are motivated by applications in software and network testing. A strength three mixed covering array C is a k×n array with the cells of row i is filled up with elements from Zgi and having the property that in each 3×n subarray, every 3×1 column appears at least once. In this article, we consider a generalization of strength-3 mixed covering arrays that allows a 3-uniform hypergraph structure which specifies the choices of 3×n subarrays in C. The number of columns in such array is called its size . Given a weighted 3-uniform hypergraph H , a strength three mixed covering array on H with minimum size is called optimal . We give upper and lower bounds on the size of strength three mixed covering arrays on 3-uniform hypergraphs based on hypergraph homomorphisms. We construct optimal strength-3 mixed covering arrays on 3-uniform hypertrees, interval, and cycle hypergraphs.