From Conflicts to Diagnoses: An Empirical Evaluation of Minimal Hitting Set Algorithms

Abstract

Using appropriate models, minimal hitting sets of a set of conflict sets can provide a sound founda-tion for diagnostic reasoning. Related diagnoses can explain encountered inconsistencies between expected and experienced behavior, so that a mul-titude of algorithms for computing such diag-noses have been developed. Motivated by a lack of a comparative study, in this paper, we evaluate a selection of relevant algorithms in the context of synthetic and real-world test scenarios. 1