Session 5.3 - Test Suite Minimization

What is Test Suite Minimization?

Test suite minimization is the process of permanently reducing the size of a test suite by removing redundant or obsolete test cases while preserving its fault-detection capability and coverage criteria.

Minimization vs. related concepts:

Concept	Operation	Effect on Suite	Reversibility
Minimization (this session)	Permanently remove redundant cases	Suite T becomes permanently smaller T′	Irreversible (archive required)
Test Case Selection (Session 4.7)	Temporarily exclude cases for one regression cycle	Subset used per cycle; full T preserved	Reversible — full T rerun any time
Test Case Prioritization (Sessions 5.5–5.6)	Reorder cases; no removal	Same size; different execution order	N/A — no cases removed

Key constraint: Minimization must be coverage-preserving. The minimized suite T′ must satisfy the same coverage criterion as the original suite T. A minimized suite that drops below the coverage threshold is not a valid minimization — it is a coverage regression.

The Formal Minimization Problem

The test suite minimization problem can be stated formally as a set-cover problem:

Given:

T = the existing test suite (set of test cases t₁, t₂, …, t_n)
R = the set of coverage requirements (statements, branches, partitions, etc.) r₁, r₂, …, r_m
cov(t_i) = the set of requirements covered by test case t_i

Find: The smallest subset T′ ⊆ T such that:

∀ r ∈ R, ∃ t ∈ T′ such that r ∈ cov(t)
i.e., every requirement in R is covered by at least one case in T′

This is the minimum set-cover problem — provably NP-hard in the general case. In practice, near-optimal solutions are found with greedy or ILP approaches.

Coverage requirements R can be defined at multiple granularities:

Granularity	R elements	Aggressiveness
Statement coverage	Each executable statement	Least aggressive: widest definition of redundancy
Branch coverage	Each true/false branch outcome	Moderate: more cases are needed to cover all branches
Equivalence partition coverage	Each equivalence class	Moderate: partition-identical cases are redundant
Requirement coverage	Each functional requirement or user story	Least aggressive: only cases with no unique requirement link are redundant

Prerequisites for Safe Minimization

Minimization applied without the right inputs can silently degrade coverage. Four prerequisites must be verified before beginning:

Prerequisite 1: Execution baseline — Every case in T must have been executed against the current version of the product, and results recorded. Without this, it is impossible to distinguish a redundant case from a case that was never run.

Prerequisite 2: Coverage data — The coverage profile of each case (which statements/branches/partitions it exercises) must be available from the baseline run. This is the input to the minimization algorithm.

Prerequisite 3: Traceability links — Each case must be linked to at least one requirement or risk item. Cases without traceability are orphan candidates, not minimization candidates — they must be investigated before removal.

Prerequisite 4: Archive and version control — The archive location for removed cases must be established and accessible. Removed cases must be recoverable if minimization analysis turns out to be wrong.

Minimization Techniques Overview

Technique	Basis	Optimality	Practical Use
Greedy Set Cover	Coverage matrix; iterative selection	Near-optimal (log factor guarantee)	Most widely used; scalable
Integer Linear Programming (ILP)	Formal optimisation model	Optimal (exact minimum)	Small/medium suites; research
Clustering-Based	Test case similarity (inputs, coverage)	Heuristic	Large suites; when coverage data is unavailable
History-Based	Execution history; defect-finding rate	Heuristic	Mature suites with rich CI history

Greedy Set Cover Algorithm

Greedy Minimization

Algorithm:

Build coverage matrix M where M[i][j] = 1 if test case t_i covers requirement r_j.
Initialise T′ = ∅; R′ = R (uncovered requirements).
While R′ ≠ ∅:
- Select the test case t_k ∈ T that covers the largest number of requirements still in R′.
- Add t_k to T′.
- Remove all requirements covered by t_k from R′.
T′ is the greedy minimized suite. All cases in T \ T′ are candidates for removal.

Worked micro-example:

Suite T = {t1, t2, t3, t4, t5}. Requirements R = {r1, r2, r3, r4, r5}. Coverage matrix:

	r1	r2	r3	r4	r5	Count
t1	1	1	0	0	1	3
t2	0	1	1	1	0	3
t3	1	0	0	1	0	2
t4	0	0	1	0	1	2
t5	1	1	1	0	0	3

Iteration 1: t1, t2, t5 all cover 3 requirements. Choose t1 (or t2; tie-break). T′ = {t1}. R′ = {r3, r4} (r1, r2, r5 now covered).

Iteration 2: Remaining uncovered: r3, r4. t2 covers both. T′ = {t1, t2}. R′ = ∅. Done.

Minimized suite: T′ = {t1, t2}. Cases t3, t4, t5 are redundant candidates. Suite reduced from 5 to 2 cases (60% reduction) with full requirement coverage preserved.

ILP-Based Minimization

Integer Linear Programming

Formulation:

Decision variable: x_i ∈ {0,1} where x_i = 1 means test case t_i is included in T′.
Objective: Minimise ∑_i x_i (minimise number of selected cases)
Constraint for each requirement r_j: ∑_{i: M[i][j]=1} x_i ≥ 1 (at least one case covering r_j is selected)

ILP finds the provably optimal (smallest) T′. For the micro-example above, ILP would find the same {t1, t2} solution. For larger suites, ILP can find solutions that are 5–20% smaller than the greedy solution but requires more computation time.

When to use ILP:

Suite size < ~5,000 cases (ILP solvers are practical at this scale).
The minimization is a one-time or infrequent operation (not per-commit).
Maximum reduction is required (e.g., safety-critical system with strict execution time budget).

Clustering-Based Minimization

Clustering Approach

Concept: Group test cases by similarity (using input distance metrics or coverage overlap). From each cluster, retain one representative case and archive the rest.

Similarity metrics:

Coverage Jaccard similarity: sim(t_i, t_j) = |cov(t_i) ∩ cov(t_j)| / |cov(t_i) ∪ cov(t_j)|. Cases with Jaccard similarity > threshold θ are clustered together.
Input distance: For numeric inputs, Euclidean or Manhattan distance between test data vectors.

When to use: When structural coverage data is unavailable (black-box or legacy suites) but test data is available. Also useful as a pre-filter before greedy/ILP to reduce problem size.

History-Based Minimization

History-Based Approach

Concept: Use execution history to estimate the fault-detection contribution of each test case. Cases that have never detected a defect and are covered by another case that has are candidates for removal.

Metric: Defect Detection Contribution (DDC):

DDC(t_i) = (number of unique defects detected only by t_i) / (total defects detected by the suite)

Cases with DDC = 0 and coverage subsumed by another case are strong removal candidates.

Caution: A case with DDC = 0 is not necessarily redundant. It may cover a partition that has simply not had a defect injected in recent history. DDC-based decisions must be combined with coverage analysis, not used alone.

The Safe Minimization Process

Minimization is irreversible if not done carefully. The following 6-step process ensures no coverage is inadvertently lost:

1

Establish baseline — Run the full suite T against the current product version. Record all pass/fail results and coverage data. This is the reference point.

2

Build coverage matrix — For each test case, record which requirements/statements/branches it covers. This can be generated automatically from coverage tools (e.g., coverage.py, JaCoCo, Istanbul).

3

Apply minimization algorithm — Use greedy or ILP to identify the candidate set for removal (T \ T′). Do not remove yet.

4

Verify coverage preservation — Run the minimized candidate T′ (without the removed cases) and confirm: (a) all previously passing cases still pass, (b) coverage criterion is fully met, (c) no requirement is left uncovered.

5

Archive, don't delete — Move cases identified for removal to an archive (a dedicated folder or branch in version control, tagged with archive date and reason). Do not permanently delete.

6

Monitor and review — Over the next 2–3 sprints, monitor defect detection rate. If the minimized suite misses a defect that an archived case would have caught, restore the case. If no issues arise, the archive may be cleaned up after an agreed retention period.

The golden rule: A test case removed from the active suite should be in the archive for a minimum of one full product release cycle before permanent deletion is considered.

Choosing a Coverage Criterion for Minimization

The choice of coverage criterion determines how aggressively the suite can be minimized and what risks are accepted:

Criterion	Minimization Aggressiveness	Risk of Over-Removal	Best For
Statement coverage	Very high (smallest T′)	High: misses branch and partition nuances	Quick first pass; identifying obvious redundancy
Branch coverage	High	Medium: branch coverage preserves more than statement	Most commercial software; standard minimization target
Equivalence partition coverage	High	Low: partition-preserving minimization is semantically well-grounded	Black-box suites; requirement-driven testing
Requirement coverage	Low (least aggressive)	Very low: only cases with entirely duplicate requirement links are removed	Conservative minimization for safety-critical systems
MC/DC coverage	Low	Very low	Safety-critical; avionics, medical devices

Recommended practice: Use equivalence partition coverage as the primary criterion for most commercial software minimization. It is semantically meaningful (grounded in the specification), aggressively reduces data-clone redundancy, and has a lower risk of over-removal than pure structural criteria.

Worked Example: Minimizing a Discount Module Suite

Scenario: The discount calculation module has 12 test cases. Run the greedy algorithm using branch coverage as the criterion.

Coverage matrix (branches B1–B8):

Test Case	B1	B2	B3	B4	B5	B6	B7	B8	Coverage Count
TC-D01	1	1	0	0	1	0	0	0	3
TC-D02	1	0	1	0	0	1	0	0	3
TC-D03	0	1	1	1	0	0	1	0	4
TC-D04	0	0	0	1	1	0	0	1	3
TC-D05	1	1	0	0	0	0	0	0	2
TC-D06	0	0	1	1	0	1	0	0	3
TC-D07	0	0	0	0	1	1	1	0	3
TC-D08	1	0	0	0	0	0	1	1	3
TC-D09	0	1	0	0	1	0	0	1	3
TC-D10	0	0	1	0	0	1	1	0	3
TC-D11	1	0	0	1	0	0	0	1	3
TC-D12	0	1	1	0	0	0	1	0	3

Greedy algorithm execution:

Iteration	Best Case	New Branches Covered	Remaining Uncovered
1	TC-D03 (4 branches)	B2, B3, B4, B7	B1, B5, B6, B8
2	TC-D04 (covers B4, B5, B8 — 3 new: B5, B8)	B5, B8	B1, B6
3	TC-D02 (covers B1, B3, B6 — 2 new: B1, B6)	B1, B6	∅

Minimized suite T′ = {TC-D03, TC-D04, TC-D02} — 3 cases cover all 8 branches. The remaining 9 cases (TC-D01, TC-D05 through TC-D12 except TC-D02/03/04) are redundant candidates. Suite reduced from 12 to 3 cases (75% reduction) with 100% branch coverage preserved.

Common Mistakes

Minimizing without a baseline run
If the full suite has not been run recently, coverage data is stale. Changes to the product since the last run may mean the coverage matrix no longer reflects current code. Always regenerate coverage data immediately before minimization.

Deleting instead of archiving
Permanently deleting cases before a full release cycle has passed is the most common and most dangerous mistake. Archive is mandatory. A case that "looks redundant" may catch a defect type that the retained cases miss.

Minimizing to statement coverage only
Statement coverage is the least discriminating criterion. Two cases covering the same statements may test different branches. Statement-only minimization can remove cases that cover unique branches.

Treating greedy result as provably optimal
The greedy algorithm is near-optimal but not exact. It may retain more cases than necessary. If exact minimization is required, use ILP. Do not present greedy results as "the minimum possible suite".

Not verifying coverage after removal
Step 4 of the safe process (coverage verification) is often skipped due to time pressure. Without it, there is no guarantee that the minimized suite actually meets the stated criterion.

One-time minimization without ongoing governance
A minimized suite will re-bloat over time if the growth drivers from Session 5.2 are not addressed. Minimization is a periodic maintenance activity, not a one-off fix.

Class Activity

Coverage matrix for a User Registration module (6 cases, 6 branches):

Test Case	B1: email valid	B2: email invalid	B3: pwd length OK	B4: pwd too short	B5: username unique	B6: username taken
TC-REG-01	1	0	1	0	1	0
TC-REG-02	1	0	1	0	0	1
TC-REG-03	0	1	1	0	1	0
TC-REG-04	1	0	0	1	1	0
TC-REG-05	0	1	0	1	0	1
TC-REG-06	1	0	1	0	1	0

Tasks:

Apply the greedy set-cover algorithm step by step. Show each iteration: which case is selected, which branches are newly covered, and what remains uncovered.
Identify the minimized suite T′ and all cases in T \ T′ (removal candidates).
Verify: does T′ achieve 100% branch coverage? Show the coverage count for T′.
TC-REG-06 appears to be a data-clone of TC-REG-01. What additional analysis would you perform to confirm this before archiving TC-REG-06?
Describe the 6-step safe minimization process you would follow to remove the cases identified in step 2. What would you do differently for TC-REG-06 (clone) vs. TC-REG-05 (structurally subsumed)?

Exit Ticket

State the formal minimization problem in one sentence using the notation T, T′, R, and cov(t_i).
A team applies greedy minimization with statement coverage and reduces 100 cases to 30. A colleague argues the result is not safe because branch coverage was not verified. Is the colleague correct? Explain.
What is the difference between archiving and deleting a removed test case? Why does it matter?
Can minimization be applied to a suite that has never been run? Why or why not?

Summary & Assignment

Test suite minimization permanently removes redundant test cases while preserving the coverage criterion. The formal problem is a set-cover optimisation; the greedy algorithm provides near-optimal solutions efficiently. ILP provides exact solutions for smaller suites. Clustering and history-based methods handle cases where coverage data is unavailable. The safe process — baseline, coverage matrix, algorithm, verification, archive, monitor — prevents the most common failure mode: accidental coverage loss.

Key takeaways:

Minimization ≠ selection: minimization is permanent; selection is per-cycle.
Prerequisite: every case must have a recent execution baseline and coverage profile.
Greedy set-cover is the standard practical algorithm: O(n log m) time, (1 + ln m)-approximation guarantee.
The coverage criterion determines aggressiveness: branch > statement for safety; partition coverage for specification-based suites.
Archive before delete; monitor for one full release cycle before permanent removal.

Assignment (Session 5.3):

For the redundant cases identified in your Session 5.2 assignment, build a coverage matrix using branch coverage. Apply the greedy algorithm manually (or use a coverage tool's output). Report the resulting T′ size and the percentage reduction.
Verify that T′ achieves the same branch coverage percentage as the original T. Document any discrepancy and explain its cause.
For 3 cases in T \ T′, document the specific redundancy type (data-clone, subsumed, orphaned) and the evidence that justifies classification.
Describe the archive strategy you would implement for your project. What metadata would you store with each archived case, and what is the retention period before permanent deletion?

Test Suite Minimization

Learning Objectives