On the practical performance of minimal hitting set algorithms from a diagnostic perspective

Ingo Hans Pill, Thomas Quaritsch, Franz Wotawa

Research output: Contribution to journalArticlepeer-review


Minimal hitting sets (MHSs) meliorate our reasoning in many applications, including AI planning, CNF/DNF conversion, and program debugging. When following Reiter’s ”theory of diagnosis from first principles”, minimal hitting sets are also essential to the diagnosis problem, since diagnoses can be characterized as the minimal hitting sets of conflicts in the behavior of a faulty system. While the large amount of application options led to the advent of a variety of corresponding MHS algorithms, for diagnostic purposes we still lack a comparative evaluation assessing performance characteristics. In this paper, we thus empirically evaluate a set of complete algorithms relevant for diagnostic purposes in synthetic and real-world scenarios. We consider in our experimental evaluation also how cardinality constraints on the solution space, as often established in practice for diagnostic purposes, influence performance in terms of run-time and memory usage.

Original languageEnglish
Number of pages15
JournalInternational Journal of Prognostics and Health Management
Issue number2
Publication statusPublished - 2016

ASJC Scopus subject areas

  • Computer Science (miscellaneous)

Fields of Expertise

  • Information, Communication & Computing

Cite this