Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma

DOI10.1016/J.TCS.2019.10.022zbMATH Open1487.05042arXiv1901.05386OpenAlexW2980425835WikidataQ124832901 ScholiaQ124832901MaRDI QIDQ2333832FDOQ2333832

Authors: Lucia Moura, Sebastian Raaphorst, Brett Stevens 

Publication date: 13 November 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Covering arrays are generalizations of orthogonal arrays that have been widely studied and are used in software testing. The probabilistic method has been employed to derive upper bounds on the sizes of minimum covering arrays and give asymptotic upper bounds that are logarithmic on the number of columns of the array. This corresponds to test suites with a desired level of coverage of the parameter space where we guarantee the number of test cases is logarithmic on the number of parameters of the system. In this paper, we study variable strength covering arrays, a generalization of covering arrays that uses a hypergraph to specify the sets of columns where coverage is required; (standard) covering arrays is the special case where coverage is required for all sets of columns of a fixed size $t$, its strength. We use the probabilistic method to obtain upper bounds on the number of rows of a variable strength covering array, given in terms of parameters of the hypergraph. We then compare this upper bound with another one given by a density-based greedy algorithm on different types of hypergraph such as $t$-designs, cyclic consecutive hypergraphs, planar triangulation hypergraphs, and a more specific hypergraph given by a clique of higher strength on top of a "base strength". The conclusions are dependent on the class of hypergraph, and we discuss specific characteristics of the hypergraphs which are more amenable to using different versions of the Lov'{a}sz local lemma.

Full work available at URL: https://arxiv.org/abs/1901.05386

Recommendations

• The Lovász local lemma and variable strength covering arrays
• Upper bounds on the size of covering arrays
• The Lovász local lemma and its applications to some combinatorial arrays
• \(t\)-covering arrays generated by a tiling probability model
• Small arrays of maximum coverage
• Asymptotic size of covering arrays: an application of entropy compression
• t-Covering Arrays: Upper Bounds and Poisson Approximations
• On the algorithmic Lovász local lemma and acyclic edge coloring

zbMATH Keywords

greedy algorithmderandomizationcovering arraysvariable strengthLovász local lemma

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Other designs, configurations (05B30) Combinatorics on words (68R15)

Cites Work

• The CRC handbook of combinatorial designs
• Title not available (Why is that?)
• Probabilistic methods for algorithmic discrete mathematics
• Binary consecutive covering arrays
• t-Covering Arrays: Upper Bounds and Poisson Approximations
• Counting designs
• Title not available (Why is that?)
• Asymptotic lower bounds for Ramsey functions
• A constructive proof of the general Lovász local lemma
• A construction for strength-3 covering arrays from linear feedback shift register sequences
• Variable strength covering arrays
• Upper bounds on the size of covering arrays
• Asymptotic size of covering arrays: an application of entropy compression
• Constructing new covering arrays from LFSR sequences over finite fields
• Asymptotic and constructive methods for covering perfect hash families and covering arrays
• Covering array bounds using analytical techniques
• The Lovász local lemma and variable strength covering arrays
• Consecutive covering arrays and a new randomness test
• Two-stage algorithms for covering array construction

Cited In (6)

• A construction of variable strength covering arrays
• Algorithmic methods for covering arrays of higher index
• The Lovász local lemma and variable strength covering arrays
• The Lovász local lemma and its applications to some combinatorial arrays
• Upper bounds on the size of covering arrays
• The Stein-Lovász theorem and its applications to some combinatorial arrays

Uses Software

• OpenOpt

This page was built for publication: Upper bounds on the sizes of variable strength covering arrays using the Lovász local lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2333832)