Skip to content

Home / Concepts / NCK Optimization

NCK Post-Optimization

The NCK (Nayeri-Colbourn-Konjevod) algorithm is a post-generation optimization that attempts to remove redundant test cases from a covering array while maintaining complete t-way coverage. It is based on the paper Nayeri, P., Colbourn, C.J., and Konjevod, G. (2013) — "Randomized post-optimization of covering arrays." European Journal of Combinatorics, vol. 34, pp. 91-103.

Effectiveness

In practice, NCK rarely reduces the number of test cases when applied to arrays generated by SIPO or PICT at pairwise strength (t=2). Both engines already produce near-optimal arrays for pairwise coverage, leaving little redundancy to exploit. NCK may be more effective at higher interaction strengths (t=3+) where the generated arrays have more room for improvement.

How It Works

After a covering array is generated, some test cases may be redundant — every tuple they cover is also covered by other test cases in the array. The NCK algorithm identifies and removes these redundant rows.

  1. Build tuple index — Catalog every t-way tuple and which rows cover it
  2. Count coverage — For each row, check if every tuple it covers has count > 1 (meaning another row also covers it)
  3. Remove redundant rows — If a row's tuples are all covered elsewhere, it can be safely removed
  4. Repeat — Continue passes until no more rows can be removed

Key Properties

  • Coverage guarantee — The reduced array still covers all t-way tuples
  • Seed preservation — Seeded rows are never removed
  • Constraint respect — Only removes rows, never modifies values
  • Randomized exploration — Shuffles row order between passes for better results

Using NCK in the UI

After generating results, click Reduce using NCK on the Results tab. A progress dialog shows:

  • Current pass number
  • Rows removed so far
  • Elapsed time

Press Escape to cancel and keep the best result found so far.

When to Use

NCK is most effective when:

  • The initial generation used the PICT engine (SIPO results are often already near-optimal)
  • The model has many parameters with few values each
  • You need the absolute minimum test case count and can afford the extra processing time

Typical Results

NCK rarely removes test cases from arrays generated at pairwise strength (t=2), because both PICT and SIPO already produce compact arrays with minimal redundancy at that level. At higher interaction strengths, there may be more opportunity for reduction, but results depend heavily on the model structure.