EC-MHS: Equivalence-Based Compression for Minimal Hitting Set Enumeration in Model-Based Diagnosis

Enumerating all inclusion-minimal hitting sets is a fundamental combinatorial task that arises in areas such as model-based diagnosis, hypergraph dualization, and data mining. In conflict-driven model-based diagnosis, exact enumeration becomes a computational bottleneck when both the component set and the diagnosis family are large. Existing exact methods mainly exploit conflict reuse or conflict-family structure, while component equivalence has rarely been integrated into search, output representation, and partition maintenance as a unified mechanism. This paper presents EC-MHS, an equivalence-aware framework for minimal hitting set enumeration in diagnosis. It combines Static Twin Compression (STC), which exploits coverage-signature symmetry among components to reduce the representative search space before enumeration, Dynamic Twin Compression (DTC) to merge candidates whose residual-state symmetry renders them interchangeable during search, a Compact Diagnosis Family Representation (CDFR) for exact weight-based aggregation and lossless class-wise expansion at the STC level, and iSTC to maintain the static partition under monotonic conflict addition. Experiments on ISCAS-85 benchmark circuits show that static equivalence appears in at least 96% of the dataset instances and that STC reduces the number of search candidates by 69–87% before search. On redundancy-rich benchmark instances, DTC reduces runtime by up to 75%, and iSTC maintains the STC partition 24 times faster than a full rebuild.