On the Covering Array Number of $3$-uniform Qualitative Independence Hypergraphs

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, Birla Institute of Technology and Science Pilani, K K Birla Goa Campus, Sancoale, Goa, India.

Abstract

Covering arrays (CAs) are widely recognized combinatorial designs that facilitate efficient test suite generation in software testing. For a positive integer $n$ and a set $S$ of size $g$, a \emph{covering array on a hypergraph} $H = (V, E)$ of size $n$ and alphabet size $g$, denoted $CA(n, H, g)$, is an $n \times |V|$ array with entries from $S$, where columns correspond to the vertices in $V$, such that for every hyperedge $e \in E$ of size $m$, the sub-array indexed by the vertices of $e$ contains all the ordered $m$-tuples from $S^m$ at least once, as a row. The smallest $n$ for which such an array exists is the \emph{covering array number of $H$}, denoted $CAN(H, g)$. This parameter represents the minimal test suite size for practical applications. For a $t$-uniform hypergraph $H$ and positive integers $g$ and $n$, a $CA(n, H, g)$ exists if and only if there is a hypergraph homomorphism from $H$ to $t\text{-}QI(n, g)$, a distinctive class of hypergraphs called \emph{qualitative independence hypergraphs}. Consequently, for such a hypergraph $H$, $CAN(H, g) \leq CAN(t\text{-}QI(n,g),g)$. In this paper, we develop a technique to determine the strong chromatic number and the size of the largest $3$-cliques of $3\text{-}QI(n, 2)$ to establish that $CAN(3\text{-}QI(n, 2),2)=n$ for some values of $n$ and apply the results obtained to find the covering array number of certain classes of hypergraphs.

Keywords

Main Subjects

References

[1] Y. Akhtar, A hyperedge coloring and application in combinatorial testing, AKCE Int. J. Graphs Comb. 19 (2022), no. 2, 125–132. https://doi.org/10.1080/09728600.2022.2081523
[2] Y. Akhtar and S. Maity, Mixed covering arrays on 3-uniform hypergraphs, Discrete Appl. Math. 232 (2017), 8–22.
https://doi.org/10.1016/j.dam.2017.08.023
[3] Y. Akhtar and S. Maity, Covering array on the cartesian product of hypergraphs, Graphs Combin. 40 (2024), no. 4, Article number: 87 https://doi.org/10.1007/s00373-024-02813-5
[4] Y. Akhtar and F.K.H. Phoa, Cost-efficient mixed-level covering designs for testing experiments, J. Stat. Theory Pract. 14 (2020), Article number: 6 https://doi.org/10.1007/s42519-019-0062-7
[5] K.A. Bush, Orthogonal arrays of index unity, Ann. Math. Statist. 23 (1952), no. 3, 426–434. https://doi.org/10.1214/aoms/1177729387
[6] D.M. Cohen, S.R. Dalal, J. Parelius, and G.C. Patton, The combinatorial design approach to automatic test generation, IEEE software 13 (1996), no. 5, 83–88. https://doi.org/10.1109/52.536462
[7] C.J. Colbourn, CRC Handbook of Combinatorial Designs, CRC press, 2010.
[8] C.J. Colbourn, Covering array tables for $t = 2, 3, 4, 5, 6$, https://github.com/ugroempi/cas/blob/main/colbourntables.md, (2025).
[9] C.J. Colbourn, G. Kéri, P.P. Rivas Soriano, and J.-C. Schlage-Puchta, Covering and radius-covering arrays: Constructions and classification, Discrete Appl. Math. 158 (2010), no. 11, 1158–1180. https://doi.org/10.1016/j.dam.2010.03.008
[10] C.J. Colbourn, S.S. Martirosyan, T. Van Trung, and R.A. Walker, Roux-type constructions for covering arrays of strengths three and four, Des. Codes Crypt. 41 (2006), no. 1, 33–57. https://doi.org/10.1007/s10623-006-0020-8
[11] S.R. Dalal and C.L. Mallows, Factor-covering designs for testing software, Technometrics 40 (1998), no. 3, 234–243.
https://doi.org/10.2307/1271179
[12] P. Erdos, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.(2) 12 (1961), 313–320. https://doi.org/10.1093/qmath/12.1.313
[13] A.S. Hedayat, N.J.A. Sloane, and J. Stufken, Orthogonal Arrays: Theory and Applications, Springer Science and Business Media, New York, 2012.
[14] I.S. Honkala, Modified bounds for covering codes, IEEE Trans. Info. Theory 37 (2006), no. 2, 351–365. https://doi.org/10.1109/18.75253
[15] K.A. Johnson and R. Entringer, Largest induced subgraphs of the n-cube that contain no 4-cycles, J. Combin. Theory Ser. B 46 (1989), no. 3, 346–355. https://doi.org/10.1016/0095-8956(89)90054-3
[16] L. Kampel and D.E. Simos, A survey on the state of the art of complexity problems for covering arrays, Theor. Comput. Sci. 800 (2019), 107–124. https://doi.org/10.1016/j.tcs.2019.10.019
[17] G.O. Katona, Two applications (for search theory and truth functions) of Spencer type theorems, Period. Math. Hungar. 3 (1973), no. 1, 19–26. https://doi.org/10.1007/BF02018457
[18] D.J. Kleitman and J. Spencer, Families of k-independent sets, Discrete Math. 6 (1973), no. 3, 255–262.
https://doi.org/10.1016/0012-365X(73)90098-8
[19] J.I. Kokkala, K. Meagher, R. Naserasr, K.J. Nurmela, P.R. Östergård, and B. Stevens, On the structure of small strength-2 covering arrays, J. Combin. Des. 28 (2020), no. 1, 5–24. https://doi.org/10.1002/jcd.21671
[20] J. Korner and M. Lucertini, Compressing inconsistent data, IEEE Trans. Info. Theory 40 (2006), no. 3, 706–715.
https://doi.org/10.1109/18.335882
[21] D.R. Kuhn, R.N. Kacker, and Y. Lei, Estimating t-way fault profile evolution during testing, IEEE 40th annual computer software and applications conference (COMPSAC), vol. 2, IEEE, 2016, pp. 596–597. https://doi.org/10.1109/COMPSAC.2016.110
[22] J. Lawrence, R.N. Kacker, Y. Lei, D.R. Kuhn, and M. Forbes, A survey of binary covering arrays, Electron. J. Comb. (2011), #P84. https://doi.org/10.37236/571
[23] X.N. Lu and M. Jimbo, Arrays for combinatorial interaction testing: A review on constructive approaches, Jpn. J. Stat. Data Sci. 2 (2019), 641–667. https://doi.org/10.1007/s42081-019-00056-w
[24] K. Meagher, Covering arrays on graphs: qualitative independence graphs and extremal set partition theory, Ph.D. thesis, Ottawa-Carleton Institute of Mathematics and Statistics, 2018.
[25] K. Meagher and B. Stevens, Covering arrays on graphs, J. Combin. Theory Ser. B 95 (2005), no. 1, 134–151. https://doi.org/10.1016/j.jctb.2005.03.005
[26] National Institute of Standards and Technology, The economic impacts of inadequate infrastructure for software testing, 2002.
[27] S. Raaphorst, Variable strength covering arrays, Ph.D. thesis, University of Ottawa (Canada), 2013.
[28] S. Raaphorst, L. Moura, and B. Stevens, Variable strength covering arrays, J. Combin. Des. 26 (2018), no. 9, 417–438.
https://doi.org/10.1002/jcd.21602.
[29] G. Seroussi and N.H. Bshouty, Vector sets for exhaustive testing of logic circuits, IEEE Trans. Info. Theory 34 (1988), no. 3, 513–522. https://doi.org/10.1109/18.6031
[30] B. Stevens and E. Mendelsohn, Efficient software testing protocols, Proceedings of the 1998 conference of the Centre for Advanced Studies on Collaborative research, 1998, p. 22.
[31] A.J. Tong, Y.G. Wu, and L.D. Li, Room-temperature phosphorimetry studies of some addictive drugs following dansyl chloride labelling, Talanta 43 (1996), no. 9, 1429–1436. https://doi.org/10.1016/0039-9140(96)01905-4
[32] J. Torres-Jimenez, I. Izquierdo-Marquez, and H. Avila-George, Methods to construct uniform covering arrays, IEEE Access 7 (2019), 42774–42797. https://doi.org/10.1109/ACCESS.2019.2907057
[33] W.D. Wallis and J.C. George, Introduction to Combinatorics, Chapman and Hall/CRC, New York, 2016.
[34] A.W. Williams and R.L. Probert, A practical strategy for testing pair-wise coverage of network interfaces, Proceedings of ISSRE’96: 7th International Symposium on Software Reliability Engineering, IEEE, 1996, pp. 246–254.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 April 2026

Files

Share

How to cite

Statistics