Covering Arrays on Product Graphs

Abstract

Two vectors x, y in ℤ𝑛𝑔 are qualitatively independent if for all pairs (𝑎,𝑏)∈ℤ𝑔×ℤ𝑔, there exists 𝑖∈{1,2,…,𝑛} such that (𝑥𝑖,𝑦𝑖)=(𝑎,𝑏). A covering array on a graph G, denoted by CA(n, G, g), is a |𝑉(𝐺)|×𝑛 array on ℤ𝑔 with the property that any two rows which correspond to adjacent vertices in G are qualitatively independent. The number of columns in such array is called its size. Given a graph G, a covering array on G with minimum size is called optimal. Our primary concern in this paper is with constructions that make optimal covering arrays on large graphs that are obtained from product of smaller graphs. We consider four most extensively studied graph products in the literature and give upper and lower bounds on the size of covering arrays on product graphs. We find families of graphs for which the size of covering array on the Cartesian product graphs achieves the lower bound. Finally, we present a polynomial time approximation algorithm with approximation ratio ⌈log(|𝑉|2𝑘−1)⌉ for constructing covering array on graph 𝐺=(𝑉,𝐸) with 𝑘>1 prime factors with respect to the Cartesian product.