Abstract
In this paper, we look at covering arrays with forbidden edges (CAFEs), which are used in testing applications (software, networks, circuits, drug interaction, material mixtures, etc.) where certain combinations of parameter values are forbidden. Covering arrays are classical objects used in these applications, but the situation of dealing with forbidden configurations is much less studied. Danziger et. al. [8] have recently studied this problem and shown some computational complexity results, but left some important open questions. Around the same time, Martinez et al. [18] defined and studied error-locating arrays (ELAs), which are very related to CAFEs, leaving similar computational complexity questions. In particular, these papers showed polynomial-time solvability of the existence of CAFEs and ELAs for binary alphabets (g = 2), and the NP-hardness of these problems for g ≥ 5. This not only left open the complexity of determining optimum CAFEs and ELAs for g = 2,3,4, but some suspicion that the binary case might be solved by a polynomial-time algorithm. In this paper, we prove that optimizing CAFEs and ELAs is indeed NP-hard even when restricted to the case of binary alphabets. We also provide a hardness of approximation result. The proof strategy uses a reduction from edge clique covers of graphs (ECCs) and covers all cases of g. We also explore important relationships between ECCs and CAFEs and give some new bounds for uniform ECCs and CAFEs.
The results presented in this paper are part of the Master’s thesis of E. Maltais [17] under the supervision of L. Moura.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brigham, R., Dutton, R.: On clique covers and independence numbers of graphs. Discrete Math. 44, 139–144 (1983)
Burr, K., Young, W.: Combinatorial test techniques: table-based automation, test generation and code coverage. In: Proc. of the Intl. Conf. on Software Testing Analysis and Review, pp. 503–513 (1998)
Cawse, J.: Experimental design for combinatorial and high throughput materials development. GE Global Research Technical Report 29, pp. 769–781 (2002)
Cohen, M., Dwyer, M., Shi, J.: Interaction testing of highly-configurable systems in the presence of constraints. In: International Symposium on Software Testing and Analysis (ISSTA), London, pp. 129–139 (2007)
Colbourn, C.: Combinatorial aspects of covering arrays. Le Matematiche, Catania 58, 121–167 (2004)
Colbourn, C., Dinitz, J.: Handbook of Combinatorial Designs, Second Edition. Chapman and Hall/CRC (2007)
Dalal, S., Jain, A., Karunanithi, N., Leaton, J., Lott, C., Patton, G., Horowitz, B.: Model-based testing in practice. In: Proc. of the Intl. Conf. on Software Engineering (ICSE 1999), New York, pp. 285–294 (1999)
Danziger, P., Mendelsohn, E., Moura, L., Stevens, B.: Covering arrays avoiding forbidden edges. Theor. Comput. Sci. 410, 5403–5414 (2009)
Erdös, P., Goodman, A., Pósa, L.: The representation of a graph by set intersections. Can. J. Math. 18, 106–112 (1966)
Gyárfás, A.: A simple lower bound on edge coverings by cliques. Discrete Math. 85, 103–104 (1990)
Hartman, A., Raskin, L.: Problems and algorithms for covering arrays. Discrete Math. 284, 149–156 (2004)
Kou, L., Stockmeyer, L., Wong, C.: Covering edges by cliques with regard to keyword conflicts and intersection graphs. Commun. ACM 21(2), 135–139 (1978)
Kuhn, D., Reilly, M.: An investigation into the applicability of design of experiments to software testing. In: Proc. 27th Annual NASA/IEEE Software Engineering Workshop, NASA Goddard Space Flight Center, pp. 91–95 (2002)
Kuhn, R., Wallace, D., Gallo, A.: Software fault interactions and implications for software testing. IEEE T. Software Eng. 30(6), 418–421 (2004)
Lovász, L.: On covering of graphs. In: Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 231–236. Academic Press, New York (1968)
Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. Assoc. Comput. Mach. 41(5), 960–981 (1994)
Maltais, E.: Covering arrays avoiding forbidden edges and edge clique covers. MSc thesis, University of Ottawa (2009)
Martinez, C., Moura, L., Panario, D., Stevens, B.: Locating errors using ELAs, covering arrays, and adaptive testing algorithms. SIAM J. Discrete Math. 23, 1776–1799 (2009)
Moura, L., Stardom, J., Stevens, B., Williams, A.: Covering arrays with mixed alphabet sizes. J. Comb. Des. 11, 413–432 (2003)
Orlin, J.: Contentment in graph theory: covering graphs with cliques. Nederl. Akad. Wetensch. Proc. Ser. A 80(5), 406–424 (1977)
Williams, A., Probert, R.: A measure for component interaction test coverage. In: Proc. ACS/IEEE International Conference on Computer Systems and Applications, pp. 301–311 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Maltais, E., Moura, L. (2010). Finding the Best CAFE Is NP-Hard. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)