Introduction

Software has too many cases to test them all. A few dozen settings combine into billions of configurations; a handful of features interact in countless ways. You can't run every test — your CI pipeline would never finish, and your bill would be enormous.

So you choose. Each test you could run covers some set of requirements — code paths, feature combinations, edge cases. The goal: pick the fewest tests that together cover every requirement. Run those, skip the rest, and you've kept your safety net while slashing time and cost.

That's optimal test selection, and it's the set-cover problem wearing a QA hat: cover a universe of requirements with as few "sets" (tests) as possible. And, like set cover, it's NP-hard.

Pick the Tests

Try it. The grid shows which requirements each test covers. Click tests to add them to your suite; covered requirements light up green. Cover all of them using as few tests as you can.

<p class="hint">Each <b>test</b> covers some <b>requirements</b> (✓). Click a test to add it to your suite — covered requirements turn <span class="g">green</span>. Cover all six using as few tests as you can.</p>
<table class="cov" id="cov"></table>
<div class="meter">
  <div>Tests chosen: <b id="count">0</b></div>
  <div id="status" class="status"></div>
</div>
<div class="btns">
  <button id="min" type="button">Minimize</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.hint .g { color: #0a7d33; font-weight: 700; }
.cov { border-collapse: collapse; }
.cov th, .cov td { border: 1px solid #e2e6eb; width: 38px; height: 34px; text-align: center; font: 600 13px system-ui; }
.cov th.req { background: #f6f8fa; color: #777; }
.cov th.req.done { background: #e6f6ec; color: #0a7d33; }
.cov th.tname { background: #fff; color: #1d3557; cursor: pointer; width: 56px; font-weight: 800; }
.cov tr.sel th.tname { background: #457b9d; color: #fff; }
.cov td { cursor: pointer; color: #cdd9e2; }
.cov td.has { color: #2a9d8f; font-weight: 800; }
.cov tr.sel td.has { background: #e6f6ec; }
.meter { display: flex; gap: 1.4rem; align-items: center; margin: .8rem 0 .6rem; font-size: 1rem; flex-wrap: wrap; }
.meter b { color: #1d3557; }
.status { font-weight: 800; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Optimal test selection = set cover. Requirements are the universe; each test
// covers a subset; pick the fewest tests covering all. NP-hard; Minimize here
// brute-forces the minimum (T1,T2 cover everything -> 2 tests).
const U = 6;
const TESTS = [[0,1,2,3],[2,3,4,5],[0,1],[4,5],[0,5],[1,2,4]];
let chosen = new Set();

function covered() { const c = new Set(); chosen.forEach(i => TESTS[i].forEach(r => c.add(r))); return c; }

function render() {
  const cov = covered();
  let html = '<tr><th class="tname"></th>' + Array.from({length: U}, (_, r) => '<th class="req' + (cov.has(r) ? ' done' : '') + '">R' + (r + 1) + '</th>').join('') + '</tr>';
  TESTS.forEach((t, i) => {
    const sel = chosen.has(i);
    html += '<tr class="' + (sel ? 'sel' : '') + '"><th class="tname" data-i="' + i + '">T' + (i + 1) + '</th>';
    for (let r = 0; r < U; r++) html += '<td class="' + (t.includes(r) ? 'has' : '') + '" data-i="' + i + '">' + (t.includes(r) ? '✓' : '') + '</td>';
    html += '</tr>';
  });
  document.getElementById('cov').innerHTML = html;
  document.getElementById('cov').querySelectorAll('[data-i]').forEach(el => el.addEventListener('click', () => { const i = +el.dataset.i; chosen.has(i) ? chosen.delete(i) : chosen.add(i); render(); }));
  document.getElementById('count').textContent = chosen.size;
  const st = document.getElementById('status');
  if (cov.size === U) { st.className = 'status ok'; st.textContent = fmt('✓ All covered with %size% test%v%%v2%', { size: chosen.size, v: chosen.size === 1 ? '' : 's', v2: chosen.size <= MIN ? ' — minimal!' : ' ' + fmt('(minimum is %MIN%)', { MIN: MIN }) }); }
  else { st.className = 'status'; st.style.color = '#777'; st.textContent = fmt('%size% / %U% requirements covered.', { size: cov.size, U: U }); }
}

let MIN = U, MINSET = null;
for (let m = 1; m < (1 << TESTS.length); m++) {
  const c = new Set(); let cnt = 0;
  for (let i = 0; i < TESTS.length; i++) if (m & (1 << i)) { cnt++; TESTS[i].forEach(r => c.add(r)); }
  if (c.size === U && cnt < MIN) { MIN = cnt; MINSET = m; }
}

document.getElementById('min').addEventListener('click', () => { chosen = new Set(); for (let i = 0; i < TESTS.length; i++) if (MINSET & (1 << i)) chosen.add(i); render(); });
document.getElementById('reset').addEventListener('click', () => { chosen = new Set(); render(); });
render();
Result
Console

When everything's green, check your count, then hit Minimize to see the smallest possible suite. The obvious "pick the test that covers the most" greedy is tempting — and usually good — but it doesn't always find the true minimum. That gap is the NP-hardness showing through.

The Hard Part

Testing smartly runs straight into a famous hard problem:

  • Checking is easy. Given a chosen suite, confirm every requirement is covered by at least one test.
  • Brute force explodes. With n candidate tests there are 2n2^{n} subsets to consider — hopeless beyond small suites.
  • It's set cover. Requirements are the universe; each test is a set of the requirements it covers; you want the fewest sets covering everything. Set cover is NP-hard, so this is too.
  • Combinatorial testing adds a twist. To catch interaction bugs you often want every pair (or triple) of feature values tested together — building a minimal covering array is also NP-hard.
  • Greedy is the workhorse. Repeatedly pick the test covering the most still-uncovered requirements. It's fast and gives a logarithmic-factor approximation — provably close, and the best you can hope for unless P = NP.
  • Exact when it counts. For critical suites, integer programming finds the true minimum on moderate instances.

So optimal testing is a daily, dollars-and-minutes encounter with NP-hardness — every CI pipeline is quietly solving a set-cover problem.

Where It Matters

Leaner test suites pay off across software and hardware:

  • CI/CD cost and speed: fewer tests mean faster pipelines and lower compute bills — at scale, a huge saving.
  • Regression-test selection: after a change, run only the tests that could be affected.
  • Combinatorial / configuration testing: covering all feature-pair interactions with a tiny covering array.
  • Hardware and chip verification: choosing test vectors that exercise all the cases.
  • Safety-critical certification: proving required coverage with a justifiable, minimal suite.

Test-impact analysis and combinatorial test tools used across the industry are, under the hood, solving exactly this covering problem.

Conclusion

Optimal test selection is one of the most down-to-earth hard problems on this site — it's not about cosmic limits, it's about your build time and your cloud bill. Choose too many tests and you waste minutes and money; too few and a bug slips through. The sweet spot — full coverage, fewest tests — is exactly a set-cover problem, and set cover is NP-hard.

But this is the kind of hard we live with comfortably. Greedy gets you provably close, integer programming nails the optimum when it matters, and every fast, trustworthy CI pipeline is quietly winning a small battle against NP-hardness — so the tests that run are just enough, and no more.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/optimal-testing/Content licensed under CC BY-NC 4.0.