Covering perfect hash families and covering arrays of higher index

Document Type : 2022 CCGTA IN SOUTH FLA

Author

Computing and Augmented Intelligence, Arizona State University, PO Box 878809, Tempe, AZ, 85287-8809, U.S.A.

Abstract

By exploiting symmetries of finite fields, covering perfect hash families provide a succinct representation for covering arrays of index one. For certain parameters, this connection has led to both the best current asymptotic existence results and the best known efficient construction algorithms for covering arrays. The connection generalizes in a straightforward manner to arrays in which every $t$-way interaction is covered $\lambda > 1$ times, i.e., to covering arrays of index more than one. Using this framework, we focus on easily computed, explicit upper bounds on numbers of rows for various parameters with higher index.

Keywords

Main Subjects


[1] Y. Akhtar, C. J. Colbourn and V. R. Syrotiuk, Mixed covering, locating, and detecting arrays via cyclotomy, Proceedings of the 52nd Southeastern Conference on Combinatorics, Graph Theory and Computing, to appear.
[2] N. Alon and J. H. Spencer, The probabilistic method, Third edition, With an appendix on the life and work of Paul Erdős. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, 2008.
[3] R. C. Bose and K. A. Bush, Orthogonal arrays of strength two and three, Ann. Math. Statistics, 23 (1952) 508–524.
[4] R. C. Bryce and C. J. Colbourn, The density algorithm for pairwise interaction testing, Softw. Test. Verifi-cation Reliab., 17 (2007) 159–182.
[5] R. C. Bryce and C. J. Colbourn, A density-based greedy algorithm for higher strength covering arrays, Softw. Test. Verification Reliab., 19 (2009) 37–53.
[6] K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Statistics, 23 (1952) 426–434.
[7] M. A. Chateauneuf, C. J. Colbourn and D. L. Kreher, Covering arrays of strength three, Des. Codes Cryptogr., 16 (1999) 235–242.
[8] M. A. Chateauneuf and D. L. Kreher, On the state of strength-three covering arrays, J. Combin. Des., 10 (2002) 217–238.
[9] D. M. Cohen, S. R. Dalal, M. L. Fredman and G. C. Patton, The AETG system: An approach to testing based on combinatorial design, IEEE Trans. Software Eng., 23 (1997) 437–444.
[10] C. J. Colbourn, Covering array tables:2 ≤ v ≤ 25, 2 ≤ t ≤ 6, t ≤ k ≤ 10000, 2005-23. https://www.public.asu.edu/ccolbou/src/tabby.
[11] C. J. Colbourn, Strength two covering arrays: existence tables and projection, Discrete Math., 308 (2008) 772–786.
[12] C. J. Colbourn, Covering arrays from cyclotomy, Des. Codes Cryptogr., 55 (2010) 201–219.
[13] C. J. Colbourn, Conditional expectation algorithms for covering arrays, J. Combin. Math. Combin. Comput., 90 (2014) 97–115.
[14] C. J. Colbourn and E. Lanus, Subspace restrictions and affine composition for covering perfect hash families, Art Discrete Appl. Math., 1 (2018) 19 pp.
[15] C. J. Colbourn, E. Lanus and K. Sarkar, Asymptotic and constructive methods for covering perfect hash families and covering arrays, Des. Codes Cryptogr., 86 (2018) 907–937.
[16] C. J. Colbourn and D. W. McClary, Locating and detecting arrays for interaction faults, J. Comb. Optim., 15 (2008) 17–48.
[17] C. J. Colbourn and V. R. Syrotiuk, On a combinatorial framework for fault characterization, Math. Comput. Sci., 12 (2018) 429–451.
[18] S. Das and T. Mészáros, Small arrays of maximum coverage, J. Combin. Des., 26 (2018) 487–504.
[19] D. Deng, D. R. Stinson and R. Wei, The Lovász local lemma and its applications to some combinatorial arrays, Des. Codes Cryptogr., 32 (2004) 121–134.
[20] M. S. Donders and A. P. Godbole, t-covering arrays generated by a tiling probability model, Congr. Numer., 218 (2013) 111–116.
[21] R. E. Dougherty, An asymptotically optimal bound for covering arrays of higher index, 2022. arXiv:2211.01209.
[22] R. E. Dougherty and C. J. Colbourn, Perfect hash families: the generalization to higher indices, Discrete mathematics and applications, Springer Optim. Appl., 165, Springer, Cham, 2020 177–197.
[23] R. E. Dougherty, K. Kleine, M. Wagner, C. J. Colbourn, and D. E. Simos, Algorithmic methods for covering arrays of higher index, J. Comb. Optim., 45 (2023) 21 pp.
[24] P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), I, II, III, Colloq. Math. Soc. János Bolyai, 10, North-Holland, Amsterdam-London, 1975 609–627.
[25] N. Francetić and B. Stevens, Asymptotic size of covering arrays: an application of entropy compression, J. Combin. Des., 25 (2017) 243–257.
[26] L. Gargano, J. Körner and U. Vaccaro, Sperner capacities, Graphs Combin., 9 (1993) 31–46.
[27] A. P. Godbole, D. E. Skipper and R. A. Sunley, t-covering arrays: upper bounds and Poisson approximations, Combin. Probab. Comput., 5 (1996) 105–118.
[28] A. Hartman, Software and hardware testing using combinatorial covering suites, Graph theory, combinatorics and algorithms, Springer, New York, 2005 237–266.
[29] I. Izquierdo-Marquez, J. Torres-Jimenez, B. Acevedo-Juárez and H. Avila-George, A greedy-metaheuristic 3-stage approach to construct covering arrays, Inf. Sci., 460-461 (2018) 172–189.
[30] D. S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9 (1974) 256–278.
[31] D. R. Kuhn, R. Kacker and Y. Lei, Introduction to Combinatorial Testing, CRC Press, Boca Raton, FL, 2013.
[32] J. R. Lobb, C. J. Colbourn, P. Danziger, B. Stevens and J. Torres-Jimenez, Cover starters for covering arrays of strength two, Discrete Math., 312 (2012) 943–956.
[33] L. Lovász, On the ratio of optimal integral and fractional covers, Discrete Math., 13 (1975) 383–390.
[34] C. Martı́nez, L. Moura, D. Panario and B. Stevens, Locating errors using ELAs, covering arrays, and adaptive testing algorithms, SIAM J. Discrete Math., 23 (2009/10) 1776–1799.
[35] K. Meagher and B. Stevens, Group construction of covering arrays, J. Combin. Des., 13 (2005) 70–77.
[36] R. A. Moser and G. Tardos, A constructive proof of the general Lovász local lemma, J. ACM, 57 (2010) 15 pp.
[37] L. Moura, G. L. Mullen and D. Panario, Finite field constructions of combinatorial arrays, Des. Codes Cryptogr., 78 (2016) 197–219.
[38] L. Moura, S. Raaphorst and B. Stevens, Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma, Theoret. Comput. Sci., 800 (2019) 146–154.
[39] C. Nie and H. Leung, A survey of combinatorial testing, ACM Computing Surveys, 43 (2011) 1–29.
[40] D. Panario, M. Saaltink, B. Stevens and D. Wevrick, An extension of a construction of covering arrays, J. Combin. Des., 28 (2020) 842–861.
[41] S. Raaphorst, L. Moura and B. Stevens, A construction for strength-3 covering arrays from linear feedback shift register sequences, Des. Codes Cryptogr., 73 (2014) 949–968.
[42] K. Sarkar and C. J. Colbourn, Upper bounds on the size of covering arrays, SIAM J. Discrete Math., 31 (2017) 1277–1293.
[43] K. Sarkar and C. J. Colbourn, Two-stage algorithms for covering array construction, J. Combin. Des., 27 (2019) 475–505.
[44] K. Sarkar, C. J. Colbourn, A. De Bonis and U. Vaccaro, Partial covering arrays: algorithms and asymptotics, Theory Comput. Syst., 62 (2018) 1470–1489.
[45] G. B. Sherwood, S. S. Martirosyan and C. J. Colbourn, Covering arrays of higher strength from permutation vectors, J. Combin. Des., 14 (2006) 202–213.
[46] S. K. Stein, Two combinatorial covering theorems, J. Combinatorial Theory Ser. A, 16 (1974) 391–397.
[47] J. Torres-Jimenez and I. Izquierdo-Marquez, A simulated annealing algorithm to construct covering perfect hash families, Math. Probl. Eng., 2018 (2018) 14 pp.
[48] J. Torres-Jimenez and I. Izquierdo-Marquez, Improved covering arrays using covering perfect hash families with groups of restricted entries, Appl. Math. Comput., 369 (2020) 17 pp.
[49] G. Tzanakis, L. Moura, D. Panario and B. Stevens, Constructing new covering arrays from LFSR sequences over finite fields, Discrete Math., 339 (2016) 1158–1171.
[50] E. van den Berg, E. Candès, G. Chinn, C. Levin, P. D. Olcott and C. Sing-Long, Single-photon sampling architecture for solid-state imaging sensors, Proc. Natl. Acad. Sci. USA, 110 (2013) 2752–2761.
[51] M. Wagner, C. J. Colbourn and D. E. Simos, In-parameter-order strategies for covering perfect hash families, Appl. Math. Comput., 421 (2022) 21 pp.
[52] R. A. Walker II and C. J. Colbourn, Tabu search for covering arrays using permutation vectors, J. Statist. Plann. Inference. 139 (2009) 69–80.
[53] R. Yuan, Z. Koch and A. P. Godbole, Covering array bounds using analytical techniques, Congr. Numer., 222 (2014) 65–73.
 
Volume 13, Issue 3 - Serial Number 3
2022 CCGTA IN SOUTH FLA
September 2024
Pages 293-305
  • Receive Date: 31 March 2023
  • Revise Date: 24 September 2023
  • Accept Date: 26 September 2023
  • Published Online: 01 September 2024