Pith. sign in

REVIEW 4 major objections 3 minor 56 references

The paper claims that constrained binary pairwise covering arrays can be solved to proven optimality by an integer-programming model that exploits column balance, and that a companion heuristic often matches the optimum — the first non-enum

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-08-01 19:05 UTC pith:YRLMFBSZ

load-bearing objection M0's exact model is unsound as printed—forbidden rows can slip through—though the structural bounds and the heuristic parts are worth engaging with. the 4 major comments →

arxiv 2607.17083 v1 pith:YRLMFBSZ submitted 2026-07-19 math.OC

Optimal Combinatorial Testing with Constraints: The Balancing Act

Thiago Serra , Changkun Guan , Hunter Gehman , Sumit Dhar , Mikey Ferguson , John Hooker , Marcel Schoppers This is my paper
classification math.OC MSC 90C1005B15
keywords combinatorial testingcovering arrayspairwise coverageforbidden assignmentsbalanced columnsinteger programminglower boundsconstrained test generation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tackles the problem of minimizing the number of tests needed to cover every allowed pairwise on/off combination of a set of binary components when some combinations are forbidden. It argues that the key to finding optimal test suites is still balancing each component's on/off count as much as constraints allow, and it proves necessary conditions on these counts for any valid suite. On that basis it builds an exact integer-programming model that decides, for a fixed number of tests, whether a valid suite exists, and brackets the minimum by incrementing or decrementing the test count — claimed to be the first non-enumerative exact method for the constrained case. A faster heuristic built from the same structural insights often matches the proven optimum and remains competitive with established heuristics. If correct, certified minimal test suites become practical for settings where previously only enumeration or approximation was available.

Core claim

The central claim is that optimal constrained binary pairwise covering arrays obey a sharp 'balancing' principle: every forbidden assignment (X_i,X_j)≠(α,β) forces the numbers of ones in the corresponding columns to satisfy a linear inequality (Theorem 1), e.g., forbidding (1,0) forces column i to have strictly more zeros than column j. When the constraint graph contains a complete bipartite subgraph (with a coherent partition) or a clique plus isolated vertices, stronger lower bounds on row count and column weights hold (Theorems 2 and 3). The paper then packages these into an exact integer-programming model, M0, that assigns distinct binary columns to parameters and cuts off incompatible c

What carries the argument

The load-bearing object is the balanced column — a column of the test matrix with as many zeros as ones (or, for odd N, with the imbalance limited to one). Lemma 1 shows that any set of distinct, non-complementary, balanced columns automatically covers all pairwise assignments when N is even, and this sufficiency extends to odd N via a 'least-frequent-element row' (Corollary 2). Theorem 1 translates each forbidden pair into weight inequalities on columns; Theorems 2 and 3 turn coherent complete-bipartite and clique-plus-isolated constraint graphs into lower bounds on N and on individual column weights. These results feed directly into the exact model M0, whose decision variables choose one c

Load-bearing premise

Conjecture 1 — that in some optimal covering array every parameter without pairwise constraints can be assigned a balanced column — is the uncertified premise on which the faster exact variant M1 rests; if a counterexample exists, M1 can declare a test count infeasible when a valid unbalanced solution exists.

What would settle it

A brute-force enumeration of all optimal covering arrays for small instances (e.g., k up to 6, N up to 8) with at least one unconstrained parameter, under various constraint graphs, would settle Conjecture 1: if any instance has no optimal solution in which the unconstrained parameter's column is balanced, the conjecture fails and M1's feasibility answers are not trustworthy. Alternatively, run M0 and M1 on the full instance set and look for any pair where M1 reports 'no solution at N rows' while M0 finds a valid covering array at that same N.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Certified optimal test suites: for binary pairwise testing with arbitrary forbidden pairs, a practitioner can now prove minimality instead of relying on enumeration or heuristic stopping rules.
  • Constraint-aware test counts: the paper shows adding constraints can sometimes reduce the minimum number of tests; the new bounds make such reductions detectable rather than paradoxical.
  • Structural pruning: the K_{m,n} and K_n lower bounds can be used as cutting planes or search-termination criteria in any exact or heuristic covering-array generator.
  • Heuristic speed with optimality checks: heuristic H produces solutions that, when the exact model also solves the instance, coincide with the proven optimum — giving a practical near-optimal tool for larger instances.
  • Balanced-column principle transfers: the 'balance as much as possible' rule, validated here for binary pairwise cases, gives a concrete design heuristic for other strengths and arities.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If Conjecture 1 holds, the exact variant M1 reduces the problem to selecting balanced columns for unconstrained parameters; this suggests a reformulation where unconstrained parameters are interchangeable, potentially enabling symmetry-exploiting solvers and stronger polyhedral descriptions.
  • The weight inequalities of Theorem 1 are necessary but not sufficient; a natural testable extension is to strengthen them to a complete facet description for the convex hull of feasible column-weight vectors, which could accelerate exact solving.
  • The observed decrease in optimal test count when constraints are added — e.g., from 6 rows to 5 when adding a second (1,0) constraint — has implications for test-suite minimization in evolving systems: retiring a faulty interaction may legitimately shrink the required suite, not just leave it unchanged.
  • The graph-based lower bounds (Theorems 2 and 3) might extend to non-binary parameters or higher interaction strength, since they rely only on coverage of unconstrained subproblems and the forcing logic of forbidden assignments.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The paper studies the binary pairwise covering array problem with forbidden assignments. It revisits the unconstrained case, proving necessary/sufficient conditions on column balance, and extends these to constrained problems via necessary weight inequalities (Theorem 1), lower bounds for complete-bipartite and sparse-split constraint graphs (Lemmas 4–5, Theorems 2–3), and a conjecture that unconstrained parameters can be balanced in some optimal solution (Conjecture 1). It then proposes an exact IP model M0, a conjectured-exact variant M1, a heuristic H, and a baseline IP model MB, with computational experiments on random instances. The central claim is that M0 is the first non-enumerative exact algorithm for this setting, and that H is competitive with existing heuristics.

Significance. If the M0 model were sound, the paper would make a substantive contribution to constrained combinatorial testing, providing IP-based optimality certificates where the prior exact method (Danziger et al.) is enumerative. The structural results—especially Theorem 1 and Lemmas 4–5—appear correct and are useful in their own right. The heuristic H is thoughtfully designed and the experimental comparison is broad, including several standard solvers. Credit is due for the clear separation between proven results and the conjecture, and for the attempt to derive lower bounds from graph structure. However, the exactness claim of M0 is invalid as stated because of a flaw in the incompatibility-set definition, and the baseline MB is not a faithful exact formulation. These issues directly affect the paper's main contribution.

major comments (4)
  1. [§5.2] The incompatibility set I^{(α,β)} is defined on p. 26 as pairs of columns that fail to cover at least one pairwise assignment other than (α,β). This omits the requirement that the forbidden assignment itself never appear. Consequently, two columns that cover all three allowed assignments but contain a row equal to the forbidden assignment are treated as compatible. Example: for forbidden (0,0) with N=5, c1=(0,1,1,1,0) and c2=(0,1,0,1,1) have w1=w2=3, satisfy (25f) (3+3≥6), cover (0,1) at row 5, (1,0) at row 3, and (1,1) at rows 2 and 4, yet row 1 is (0,0). Thus M0 can accept an invalid covering array and return it as a certified solution. The definition of I^{(α,β)} must also include pairs whose conjunction contains (α,β), or additional constraints must forbid rows realizing (α,β). This invalidates the exactness of M0 and the claim of optimality certificates.
  2. [§4.3] The proof of Corollary 3 miscounts the number of possible columns: it states there are 2n columns obtainable by alternating the order of assignments within n groups, but the actual number is 2^n. For n=4 this gives 16 patterns, i.e., 8 modulo complement, so m=7 unconstrained columns are possible with N=8 and α=0. A valid covering array with n=4, m=7, N=8 refutes the claimed implication m>2(n−1)→α≥1. This is a concrete false statement in the theoretical section; the corollary should be withdrawn or corrected, and claims depending on it (e.g., the extra-test threshold discussion) reassessed.
  3. [§5.4] The baseline exact model MB is not a valid formulation as written. The constraints use M_{k i1} and M_{k i2} with k as if it were a row index, but k is the number of parameters and the model defines M_{r i} with row index r. More seriously, each constraint refers to a single parameter rather than the pair: for forbidden (α,β), (26g) reads (M_{k i1}=α)→(M_{k i1}=1−β), which is a constraint on parameter i1 alone. For (α,β)=(0,0), it forces M_{k i1}≠0, i.e., parameter i1 is fixed to 1, contradicting Assumption 1 and the intended meaning. The comparison between M0 and MB is therefore not meaningful unless MB is corrected to a proper row-wise forbidden-pair formulation.
  4. [§4.4/§5.3/§7] Conjecture 1 is unproven and is load-bearing for the M1 variant. If the conjecture is false, M1 can declare an instance infeasible at N rows when a feasible solution with unbalanced unconstrained columns exists, so M1's speedups and solved-instance counts do not certify optimality. The paper does disclose the conjecture in §5.3, but the concluding claim of 'the first non-enumerative approach to obtain the optimal solution' relies on M0, whose soundness is currently broken. Moreover, since M0 and M1 agree on all solved instances, the empirical non-refutation of Conjecture 1 rests on an unsound M0. A correct exactness claim needs a proof of Conjecture 1 or a clear relegation of M1 to heuristic status.
minor comments (3)
  1. [§3.2] Typo: 'Propositon 2' should be 'Proposition 2'. Also in §3.4, 'Preposition 3' should be 'Proposition 3'.
  2. [§4] The text says 'the fourth column of M(5) has more zeros than ones', but in M(5) the last column is the unbalanced one; the fourth column has equal counts. Please correct the reference.
  3. [§6.1] No code or data repository is provided, which makes the experimental results difficult to reproduce. Consider including an artifact or a detailed instance-generation description.

Circularity Check

0 steps flagged

No significant circularity: the exact model is built from independent covering conditions; Conjecture 1 is a labeled assumption and the M0 incompatibility concern is a correctness issue, not circularity.

full rationale

Walking the derivation chain, I find no step in which a claimed output is equivalent by construction to an input. Theorem 1's weight inequalities are derived from Lemma 2 and the covering requirement; Lemma 3 and Theorems 2-3 derive lower bounds from the known unconstrained CAN values and the constraint graph; Algorithm 1's bracketing simply calls the M0 feasibility oracle. M0's compatibility constraints are stated against the covering-array definition, not fitted to the optimal row counts, and its objective only guides search. Conjecture 1 is explicitly introduced as a conjecture and used only in the conditional M1 variant; unresolved or false, it would undermine M1's exactness, but that is an unproven assumption, not a circular derivation. Section 4.3's 'full disclosure' and Section 4.4's 'we posit' transparently mark the empirical/conjectural basis. I found no load-bearing self-citations: the cited prior work (Kleitman-Spencer, Danziger et al., etc.) is external, and no uniqueness claim is imported from the authors' own prior work. Footnote 7's self-referential validation of example optimality is non-load-bearing. The skeptical M0 incompatibility-set issue would be a soundness/correctness bug if correct, but it is not a circularity pattern: the alleged omission does not reduce the claimed result to the model's own inputs. Hence score 0.

Axiom & Free-Parameter Ledger

2 free parameters · 5 axioms · 0 invented entities

The central theoretical results rest on standard combinatorial facts and the reduction assumptions; the only genuinely unproven input is Conjecture 1, used by the M1 variant. Heuristic parameters are tuning choices, not physical or fitted constants.

free parameters (2)
  • Heuristic hyperparameters C1, C2, P, TN, R1, R2, TF = C1=6, C2=4, P=9, TN=180, R1=8, R2=8, TF=60
    Chosen by the authors for the experiments; they steer the profile search and are not derived from theory. They affect which solutions are found but are not fitted to the optimal row counts.
  • Objective coefficients in models H and M0 = kN multiplier and |j - floor(N/2)| + 1 penalties
    Hand-designed to favor balanced columns; they influence which feasible solution is found when multiple exist, but they are not data-fitted constants.
axioms (5)
  • domain assumption Assumptions 1-3 and Definition 1: problems are reduced to no fixed parameters, at most one constraint per pair, and no implicit constraints.
    Any constrained problem can be preprocessed to satisfy these by fixing implied values and deriving implied constraints; standard and not restricting in principle.
  • standard math CAN(2,k,2) = min N such that k <= C(N-1, ceil(N/2)) (prior result of Kleitman-Spencer and Katona).
    Used to set the starting N in Algorithm 1 and in the lower-bound arguments.
  • ad hoc to paper Conjecture 1: parameters without pairwise constraints can be assigned balanced columns in some optimal covering array.
    Unproven; powers the M1 exact variant and part of the interpretation of the experiments.
  • standard math Duplicate rows or duplicate all-ones rows can be removed from a covering array without losing coverage.
    Used implicitly in the counting argument of Lemma 4 to obtain the CAN-1 rows with at least one zero.
  • domain assumption Complementing a parameter maps forbidden assignments coherently to (0,0) constraints in Theorems 2 and 3.
    Requires the notion of coherent partition; used to generalize the K_{m,n} and clique bounds.

pith-pipeline@v1.3.0-alltime-deepseek · 30349 in / 28499 out tokens · 258736 ms · 2026-08-01T19:05:19.738957+00:00 · methodology

0 comments
read the original abstract

Imagine that you are in front of a cockpit with several on-off buttons. If you were to thoroughly test it, you would need to try a prohibitive number of configurations. But since most bugs in practice can be isolated to interactions among few components, having tests that cover every possible pairwise configuration is a good start. However, this is a problem that goes from easy to NP-hard as soon as some pairwise configurations are forbidden. In this paper, we revisit unconstrained combinatorial testing with pairwise coverage on binary parameters and contrast it with the constrained case, showing and conjecturing properties that either are upheld or change from one to the other. In particular, we discuss the extent to which it remains a good idea -- and sometimes indeed optimal -- to have every button almost as many times on as off to minimize testing. We propose the first exact algorithm based on integer programming and a faster heuristic that often produces optimal solutions, both outperforming or competitive with their baselines.

Figures

Figures reproduced from arXiv: 2607.17083 by Changkun Guan, Hunter Gehman, John Hooker, Marcel Schoppers, Mikey Ferguson, Sumit Dhar, Thiago Serra.

Figure 1
Figure 1. Figure 1: Cumulative ratio of instances solved by each exact method over time, in [PITH_FULL_IMAGE:figures/full_fig_p030_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Pairwise comparison of solution values (numbers of rows) and timeouts [PITH_FULL_IMAGE:figures/full_fig_p031_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Pairwise comparison of runtimes and timeouts for exact methods, con [PITH_FULL_IMAGE:figures/full_fig_p032_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Pairwise comparison of solution values (numbers of rows) and timeouts, [PITH_FULL_IMAGE:figures/full_fig_p033_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Pairwise comparison of runtimes and timeouts, contrasting exact methods [PITH_FULL_IMAGE:figures/full_fig_p033_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Pairwise comparison of solution values (numbers of rows) and timeouts, [PITH_FULL_IMAGE:figures/full_fig_p034_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Pairwise comparison of time for finding the best solution and timeouts, [PITH_FULL_IMAGE:figures/full_fig_p035_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Instances solved to optimality, timed out, and proven infeasible by M [PITH_FULL_IMAGE:figures/full_fig_p036_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Difference in optimal solution value (row count) with respect to the un [PITH_FULL_IMAGE:figures/full_fig_p036_9.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

56 extracted references · 18 canonical work pages

  1. [1]

    Journal of Heuristics28(4), 377–431 (Aug 2022)

    Ansótegui, C., Manyà, F., Ojeda, J., Salvia, J.M., Torres, E.: Incomplete MaxSAT approaches for combinatorial testing. Journal of Heuristics28(4), 377–431 (Aug 2022)

    2022

  2. [2]

    In: Aguirre, A.H., Borja, R.M., Garciá, C.A.R

    Bracho-Rios, J., Torres-Jimenez, J., Rodriguez-Tello, E.: A new backtracking al- gorithm for constructing binary covering arrays of variable strength. In: Aguirre, A.H., Borja, R.M., Garciá, C.A.R. (eds.) MICAI 2009: Advances in Artificial In- telligence. pp. 397–407. Springer Berlin Heidelberg, Berlin, Heidelberg (2009)

    2009

  3. [3]

    Software Testing17(3) (2007),https://doi.org/10.1002/stvr.365

    Bryce, R.C., Colbourn, C.J.: The density algorithm for pairwise interaction testing. Software Testing17(3) (2007),https://doi.org/10.1002/stvr.365

    work page doi:10.1002/stvr.365 2007

  4. [4]

    Information and Software Technology48(10), 960– 970 (2006), Advances in Model-based Testing

    Bryce, R.C., Colbourn, C.J.: Prioritized interaction testing for pair-wise coverage with seeding and constraints. Information and Software Technology48(10), 960– 970 (2006), Advances in Model-based Testing

    2006

  5. [5]

    Bui-Xuan, B.M., Magnien, C., Meyer, P., Phan, T.H.D.: Link stream edition: Sparse split and bi-sparse split (2019),https://math.ac.vn/uploads/files /IMH20191102.pdf

    2019

  6. [6]

    John Wiley & Sons, New York (2003)

    Cawse, J.N.: Experimental Design for Combinatorial and High Throughput Mate- rials Development. John Wiley & Sons, New York (2003)

    2003

  7. [7]

    IEEE Trans

    Cohen, D.M., Dalal, S.R., Fredman, M.L., Patton, G.C.: The AETG system: An approach to testing based on combinatorial design. IEEE Trans. Software Eng.23, 437–444 (1997).https://doi.org/https://doi.org/10.1109/32.605761 38 T. Serra et al

    work page doi:10.1109/32.605761 1997

  8. [8]

    IEEE Software13(5), 83–88 (1996).https://doi

    Cohen, D., Dalal, S., Parelius, J., Patton, G.: The combinatorial design approach to automatic test generation. IEEE Software13(5), 83–88 (1996).https://doi. org/10.1109/52.536462

    work page doi:10.1109/52.536462 1996

  9. [9]

    In: 25th International Conference on Software Engineering,

    Cohen, M., Gibbons, P., Mugridge, W., Colbourn, C.: Constructing test suites for interaction testing. In: 25th International Conference on Software Engineering,

  10. [10]

    In: Proceedings of the 2007 International Sym- posium on Software Testing and Analysis

    Cohen, M.B., Dwyer, M.B., Shi, J.: Interaction testing of highly-configurable sys- tems in the presence of constraints. In: Proceedings of the 2007 International Sym- posium on Software Testing and Analysis. p. 129–139. ISSTA ’07, Association for Computing Machinery, New York, NY, USA (2007).https://doi.org/10.1145/ 1273463.1273482

    arXiv 2007

  11. [11]

    IEEE Transactions on Software Engineering34(5), 633–650 (2008).https://doi.or g/10.1109/TSE.2008.50

    Cohen, M.B., Dwyer, M.B., Shi, J.: Constructing interaction test suites for highly- configurable systems in the presence of constraints: A greedy approach. IEEE Transactions on Software Engineering34(5), 633–650 (2008).https://doi.or g/10.1109/TSE.2008.50

    work page doi:10.1109/tse.2008.50 2008

  12. [12]

    Colbourn,C.J.:Combinatorialaspectsofcoveringarrays.LeMatematiche59(1–2), 125–172 (2004)

    2004

  13. [13]

    Czerwonka, J.: Pairwise testing in real world.https://github.com/microsoft/p ict/blob/main/doc/Pairwise%20Testing%20in%20Real%20World.pdf(2006)

    2006

  14. [14]

    Theoretical Computer Science410(52), 5403–5414 (2009)

    Danziger, P., Mendelsohn, E., Moura, L., Stevens, B.: Covering arrays avoiding forbidden edges. Theoretical Computer Science410(52), 5403–5414 (2009)

    2009

  15. [15]

    In: 2017 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW)

    Duan, F., Lei, Y., Yu, L., Kacker, R.N., Kuhn, D.R.: Optimizing IPOG’s vertical growth with constraints based on hypergraph coloring. In: 2017 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW). pp. 181–188 (2017).https://doi.org/10.1109/ICSTW.2017.37

    work page doi:10.1109/icstw.2017.37 2017

  16. [16]

    Problemy Peredachi Informatskii25, 3 (10 1989)

    Dumer, I.: Asymptotically optimal codes correcting memory defects of fixed mul- tiplicity. Problemy Peredachi Informatskii25, 3 (10 1989)

    1989

  17. [17]

    In: Squillero, G., Sim, K

    Ferrer, J., Chicano, F., Alba, E.: Hybrid algorithms based on integer program- ming for the search of prioritized test data in software product lines. In: Squillero, G., Sim, K. (eds.) Applications of Evolutionary Computation. pp. 3–19. Springer International Publishing, Cham (2017)

    2017

  18. [18]

    Journal of Heuristics27(1), 229–249 (2021).https://doi.org/10.1007/s10732-020-09462 -w

    Ferrer, J., Chicano, F., Ortega-Toro, J.A.: CMSA algorithm for solving the prior- itized pairwise test data generation problem in software product lines. Journal of Heuristics27(1), 229–249 (2021).https://doi.org/10.1007/s10732-020-09462 -w

    work page doi:10.1007/s10732-020-09462 2021

  19. [19]

    In: 2011 IEEE International Conference on Computer Science and Automation Engineering

    Flores, P., Cheon, Y.: PWiseGen: Generating test cases for pairwise testing using genetic algorithms. In: 2011 IEEE International Conference on Computer Science and Automation Engineering. vol. 2, pp. 747–752 (2011).https://doi.org/10.1 109/CSAE.2011.5952610

    arXiv 2011

  20. [20]

    Software Testing, Verification and Reliability15(3) (2005),https://doi.org/10 .1002/stvr.319

    Grindal, M., Offutt, J., Andler, S.F.: Combination testing strategies: a survey. Software Testing, Verification and Reliability15(3) (2005),https://doi.org/10 .1002/stvr.319

    2005

  21. [21]

    Group in Intelligent Software Technology at Nanjing University: CCAG: A ref- erence implementation of constrained covering array generation (2021),https: //github.com/GIST-NJU/CCAG, accessed: 2026-07-14

    2021

  22. [22]

    Computer48(4), 64–72 (2015).https://doi.org/ 10.1109/MC.2015.114 Optimal Combinatorial Testing with Constraints: The Balancing Act 39

    Hagar, J.D., Wissink, T.L., Kuhn, D.R., Kacker, R.N.: Introducing combinatorial testing in a large organization. Computer48(4), 64–72 (2015).https://doi.org/ 10.1109/MC.2015.114 Optimal Combinatorial Testing with Constraints: The Balancing Act 39

    work page doi:10.1109/mc.2015.114 2015

  23. [23]

    Discrete Mathematics284(1), 149–156 (2004).https://doi.org/10.1016/j.disc.2003

    Hartman, A., Raskin, L.: Problems and algorithms for covering arrays. Discrete Mathematics284(1), 149–156 (2004).https://doi.org/10.1016/j.disc.2003. 11.029

    work page doi:10.1016/j.disc.2003 2004

  24. [24]

    Constraints11, 119–219 (2006)

    Hnich, B., Prestwich, S.D., Selensky, E., Smith, B.M.: Constraint models for the covering test problem. Constraints11, 119–219 (2006)

    2006

  25. [25]

    Kadioglu, S.: Column generation for interaction coverage in combinatorial software testing (2017),https://arxiv.org/abs/1712.07081

    Pith/arXiv arXiv 2017

  26. [26]

    Periodica Mathematica Hungarica3, 19–26 (1973)

    Katona, G.O.H.: Two applications (for search theory and truth functions) of Sperner type theorems. Periodica Mathematica Hungarica3, 19–26 (1973)

    1973

  27. [27]

    Discrete Mathematics 6(3), 255–262 (1973)

    Kleitman, D.J., Spencer, J.: Families ofk-independent sets. Discrete Mathematics 6(3), 255–262 (1973)

    1973

  28. [28]

    In: 2006 30th An- nual IEEE/NASA Software Engineering Workshop

    Kuhn, D.R., Okun, V.: Pseudo-exhaustive testing for software. In: 2006 30th An- nual IEEE/NASA Software Engineering Workshop. pp. 153–158 (2006).https: //doi.org/10.1109/SEW.2006.26

    work page doi:10.1109/sew.2006.26 2006

  29. [29]

    Kuhn, D., Kacker, R., Lei, Y.: Practical combinatorial testing. Tech. Rep. NIST SP 800-142, National Institute of Standards and Technology, Gaithersburg, MD (10 2010).https://doi.org/10.6028/NIST.SP.800-142

    work page doi:10.6028/nist.sp.800-142 2010

  30. [30]

    In: 27th Annual NASA Goddard/IEEE Software Engineering Workshop, 2002

    Kuhn, D., Reilly, M.: An investigation of the applicability of design of experiments to software testing. In: 27th Annual NASA Goddard/IEEE Software Engineering Workshop, 2002. Proceedings. pp. 91–95 (2002)

    2002

  31. [31]

    IEEE Transactions on Software Engineering30(6), 418–421 (2004).https://doi.org/10.1109/TSE.2004.24

    Kuhn, D., Wallace, D., Gallo, A.: Software fault interactions and implications for software testing. IEEE Transactions on Software Engineering30(6), 418–421 (2004).https://doi.org/10.1109/TSE.2004.24

    work page doi:10.1109/tse.2004.24 2004

  32. [32]

    The Electronic Journal of Combinatorics18(1), 1–30 (2011)

    Lawrence, J., Kacker, R.N., Lei, Y., Kuhn, D.R., Forbes, M.: A survey of binary covering arrays. The Electronic Journal of Combinatorics18(1), 1–30 (2011)

    2011

  33. [33]

    In: 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems (ECBS’07)

    Lei, Y., Kacker, R., Kuhn, D.R., Okun, V., Lawrence, J.: IPOG: A general strategy for t-way software testing. In: 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems (ECBS’07). pp. 549– 556 (March 2007).https://doi.org/10.1109/ECBS.2007.47

    work page doi:10.1109/ecbs.2007.47 2007

  34. [34]

    Software Testing, Verification and Reliability18(3), 125–148 (2008).https://doi.org/10.1002/stvr.381

    Lei, Y., Kacker, R., Kuhn, D.R., Okun, V., Lawrence, J.: IPOG/IPOG-D: Efficient test generation for multi-way combinatorial testing. Software Testing, Verification and Reliability18(3), 125–148 (2008).https://doi.org/10.1002/stvr.381

    work page doi:10.1002/stvr.381 2008

  35. [35]

    In: Proceedings Third IEEE International High-Assurance Systems Engineering Symposium (Cat

    Lei, Y., Tai, K.: In-parameter-order: a test generation strategy for pairwise testing. In: Proceedings Third IEEE International High-Assurance Systems Engineering Symposium (Cat. No.98EX231). pp. 254–261 (1998).https://doi.org/10.1109/ HASE.1998.731623

    arXiv 1998

  36. [36]

    In: 2013 IEEE International Conference on Software Maintenance

    Lopez-Herrejon, R.E., Chicano, F., Ferrer, J., Egyed, A., Alba, E.: Multi-objective optimal test suite computation for software product line pairwise testing. In: 2013 IEEE International Conference on Software Maintenance. pp. 404–407 (2013).ht tps://doi.org/10.1109/ICSM.2013.58

    work page doi:10.1109/icsm.2013.58 2013

  37. [37]

    In: 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)

    Luo, C., Lin, J., Cai, S., Chen, X., He, B., Qiao, B., Zhao, P., Lin, Q., Zhang, H., Wu, W., Rajmohan, S., Zhang, D.: AutoCCAG: An automated approach to constrained covering array generation. In: 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE). pp. 201–212 (2021).https://doi.or g/10.1109/ICSE43902.2021.00030

    arXiv 2021

  38. [38]

    Ma, L., Zhang, F., Xue, M., Li, B., Liu, Y., Zhao, J., Wang, Y.: Combinatorial testing for deep learning systems (2018),https://arxiv.org/abs/1806.07723

    Pith/arXiv arXiv 2018

  39. [39]

    In: López-Ortiz, A

    Maltais, E., Moura, L.: Finding the best cafe is np-hard. In: López-Ortiz, A. (ed.) LATIN 2010: Theoretical Informatics. pp. 356–371. Springer Berlin Heidelberg, Berlin, Heidelberg (2010) 40 T. Serra et al

    2010

  40. [40]

    National Institute of Standards and Technology: Industrial case studies - combi- natorial and pairwise testing.https://csrc.nist.gov/projects/automated-com binatorial-testing-for-software/combinatorial-methods-in-testing/cas e-studies-and-examples(2016), accessed: 2026-07-15

    2016

  41. [41]

    National Institute of Standards and Technology: Tools for combinatorial testing developed by the NIST ACTS project (2019),https://github.com/usnistgov/c ombinatorial-testing-tools, accessed: 2026-07-15

    2019

  42. [42]

    ACM Computing Surveys 43(2) (2011).https://doi.org/10.1145/1883612.1883618

    Nie, C., Leung, H.: A survey of combinatorial testing. ACM Computing Surveys 43(2) (2011).https://doi.org/10.1145/1883612.1883618

    arXiv 2011

  43. [43]

    Holden-Day (1970)

    Rényi, A.: Foundations of Probability. Holden-Day (1970)

    1970

  44. [44]

    A Tool for Parsimony in the Post-Genomics Era

    Shasha, D.E., Kouranov, A.Y., Lejay, L.V., Chou, M.F., Coruzzi, G.M.: Using Combinatorial Design to Study Regulation by Multiple Input Signals. A Tool for Parsimony in the Post-Genomics Era. Plant Physiology127(4), 1590–1594 (12 2001)

    2001

  45. [45]

    IEEE Transactions on ComputersC-32(12), 1145–1150 (1983)

    Tang, D.T., Woo, L.S.: Exhaustive test pattern generation with constant weight vectors. IEEE Transactions on ComputersC-32(12), 1145–1150 (1983)

    1983

  46. [46]

    In: Rossi, F., van Beek, P., Walsh, T

    van Beek, P.: Backtracking search algorithms. In: Rossi, F., van Beek, P., Walsh, T. (eds.)HandbookofConstraintProgramming,FoundationsofArtificialIntelligence, vol. 2, pp. 85–134. Elsevier (2006)

    2006

  47. [47]

    International Journal of Reliability, Quality and Safety Engineering08(04), 351–371 (2001).https://doi.org/10.1142/S0218539301000 58X

    Wallace, D.R., Kuhn, D.R.: Failure modes in medical device software: An analysis of 15 years of recall data. International Journal of Reliability, Quality and Safety Engineering08(04), 351–371 (2001).https://doi.org/10.1142/S0218539301000 58X

    work page doi:10.1142/s0218539301000 2001

  48. [48]

    In: Ural, H., Probert, R.L., v

    Williams, A.W.: Determination of test configurations for pair-wise interaction cov- erage. In: Ural, H., Probert, R.L., v. Bochmann, G. (eds.) Testing of Commu- nicating Systems: Tools and Techniques. IFIP TC6/WG6.1 13th International Conference on Testing of Communicating Systems (TestCom 2000), August 29– September 1, 2000, Ottawa, Canada. pp. 59–74. Sp...

    work page doi:10.1007/978-0-387-35516-0_4 2000

  49. [49]

    Wu, H., Nie, C., Petke, J., Jia, Y., Harman, M.: A survey of constrained combina- torial testing (2019),https://arxiv.org/abs/1908.02480

    Pith/arXiv arXiv 2019

  50. [50]

    IEEE Transactions on Software Engineering47(11), 2549–2562 (Nov 2021)

    Wu, H., Nie, C., Petke, J., Jia, Y., Harman, M.: Comparative analysis of constraint handling techniques for constrained combinatorial testing. IEEE Transactions on Software Engineering47(11), 2549–2562 (Nov 2021)

    2021

  51. [51]

    In: 2021 IEEE International Conference on Information Communication and Software Engineer- ing (ICICSE)

    Yang, J., Yin, S., Wang, J., Li, S.: A method for estimating minimum sizes of covering arrays avoiding forbidden edges by decomposing graphs. In: 2021 IEEE International Conference on Information Communication and Software Engineer- ing (ICICSE). pp. 185–190 (2021)

    2021

  52. [52]

    In: 2014 IEEE 15th Inter- national Symposium on High-Assurance Systems Engineering

    Yu, L., Duan, F., Lei, Y., Kacker, R.N., Kuhn, D.R.: Combinatorial test generation for software product lines using minimum invalid tuples. In: 2014 IEEE 15th Inter- national Symposium on High-Assurance Systems Engineering. pp. 65–72 (2014). https://doi.org/10.1109/HASE.2014.18

    work page doi:10.1109/hase.2014.18 2014

  53. [53]

    In: 2015 IEEE Eighth International Conference on Software Testing, Verification and Validation Workshops (ICSTW)

    Yu, L., Duan, F., Lei, Y., Kacker, R.N., Kuhn, D.R.: Constraint handling in combi- natorial test generation using forbidden tuples. In: 2015 IEEE Eighth International Conference on Software Testing, Verification and Validation Workshops (ICSTW). pp. 1–9 (2015).https://doi.org/10.1109/ICSTW.2015.7107441

    arXiv 2015

  54. [54]

    IEEE Transactions on Software Engineering28(2), 183–200 (2002)

    Zeller, A., Hildebrandt, R.: Simplifying and isolating failure-inducing input. IEEE Transactions on Software Engineering28(2), 183–200 (2002)

    2002

  55. [55]

    In: Automatic Generation of Com- binatorial Test Data

    Zhang, J., Zhang, Z., Ma, F.: The IPO family. In: Automatic Generation of Com- binatorial Test Data. pp. 41–49. Springer Berlin Heidelberg, Berlin, Heidelberg (2014).https://doi.org/10.1007/978-3-662-43429-1_4

    work page doi:10.1007/978-3-662-43429-1_4 2014

  56. [2003]

    Proceedings. pp. 38–48 (2003).https://doi.org/10.1109/ICSE.2003.1201 186

    arXiv 2003

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.