Minimal hitting set computation via hypothesis exploration

Minimal hitting set (MHS) computation is a challenging problem in conflict-oriented model-based diagnosis. This paper is a first attempt to face the problem by searching the powerset H of the conflicts’ domain, which exhibits a partial order in respect of subset inclusion. Our idea is to enhance this partial order by ordering each h in H, called a hypothesis, in each (cardinality) layer of the powerset. The overall regularity can then be exploited to process a layer at a time, according to an ascending cardinality of the hypotheses, checking whether each hypothesis is valid, and pruning all its supersets (that necessarily belong to the next layers) in one shot if it is. This is a high-level description of a template anytime algorithm that can host different methods of checking whether a given hypothesis is valid, and that is the basis not only for a monolithic computation of MHSs but also for a distributed one.