Reducibility
Glossary Contents
← Ch XIV
Chapter XV Hitting Set
Ch XVI →
  1. 43 — Hit them all
  2. 44 — Greedy in Perl
  3. 45 — Test suite minimization
45

Test suite minimization

Given thousands of regression tests covering hundreds of requirements, the smallest test suite that covers every requirement is a hitting set.

Each requirement defines a set of tests that exercise it. A regression suite that hits every requirement is a hitting set on this family. CI pipelines at Google, Facebook, and Microsoft run test minimization daily to keep cycle times under control — the optimal selection is a hitting set, the deployed heuristic is greedy. The same problem runs in threat indicator matching in SIEM systems (each malware family defined by a set of indicators of compromise; pick the smallest sensor set that catches every family), in clinical diagnostic panels (cover every condition in a differential with the fewest tests), and in fault localization (pick the smallest set of program edits that explains every failing test).

In plain terms

A team has 5,000 software tests covering 800 requirements. They want to keep the smallest set of tests that still checks every requirement at least once. The math problem is hitting set, and the running heuristic is "keep the test that covers the most still-uncovered requirements."

Scan to come back to page 45

End of Chapter XV
Chapter XVI Steiner Tree →
← 44 Greedy in Perl
3/3 · 45/63
46 The cheapest connection →