Computing the Minimal Hitting Sets Based on Dynamic Maximum Degree

A lot of theoretical and practical problems can be partly reduced to an instance of the minimal hitting set (MHS) or one of its relatives, such as the minimum set cover problem, model-based diagnosis, and teachers and courses problem. While generating MHS cluster of a collection of sets is known to be NP-hard, which necessitates heuristic approaches to handle large problems. Several exhaustive algorithms have been presented to solve the MHS problem. In this paper, we formalize the computing procedure of hitting sets by introducing SE-Tree which produces all the resolutions gradually first. As the closed nodes are added into the SE-Tree, the non-minimal hitting sets can never be produced, and the true resolutions can not be missed by pruning either. Then the concept of un-extended element degree and node degree are presented, and the node of SE-Tree is extended in accordance with the descending order of un-extended element degree. With this extended order, we not only can generate hitting set early, but also can reduce the number of generated nodes. Moreover, the node degree can be used to determine whether the set of node is a hitting set or not directly, and avoid the computing of hitting set. Results show that the corresponding algorithm is easily implemented, and the efficiency is highly improved.