Counting Minimal Unique-Cause MC/DC Test Suites for Boolean Decisions
Robin Lee, Yun-Suk Nam · IEEE Access · 2026
Unique-Cause Modified Condition/Decision Coverage (UC MC/DC) is a widely used structural adequacy criterion for safety-critical software decisions. For a Boolean decision with N atomic conditions, the theoretically minimal suite size under the one-bit witness interpretation isN+1, which is exponentially smaller than exhaustive Multiple Condition Coverage. Minimality, however, does not imply uniqueness: a single decision may admit many distinct optimal suites, while another may admit only one or none. This paper definesminimal-suite multiplicity, denoted μ(f), as the number of distinct size-(N+1) minimal suites for a decisionf, together with a feasibility-constrained variant μ(f; F). Two complementary counting views are developed: a graph-theoretic model based on colored witness edges of the Boolean hypercube, and a propositional model-counting encoding that counts minimal suites without enumerating all 2Nassignments. Exact counting is shown to be #P-complete in general under feasibility constraints. In the empirical study, exact labeled-tree enumeration remained practical forN∈ {4, 5, 6, 7} with median runtimes of 1.9×10−4s, 1.3×10−3s, 1.5×10−2s, and 2.3×10−1s per instance, respectively. A supplementary solver-based study on repeated-variable B2 instances extended the scalability picture beyond this range: exact projected counting with Ganak completed all tested cases atN= 8 andN= 10, with timeouts beginning atN= 12, while ApproxMC solved selected instances up toN= 30 but with strong instance sensitivity. Across fixedN, multiplicity varied by several orders of magnitude, and feasibility constraints sharply reduced the surviving space of optimal suites. These results position multiplicity as a quantitative indicator of robustness and substitutability among optimal UC MC/DC evidence.