The minimal hitting set generation problem: algorithms and computation
This work addresses the need for practical generation of minimal hitting sets in domains like Boolean algebra and computational biology, but it is incremental as it focuses on surveying and implementing existing algorithms.
The paper surveys twenty algorithms for generating minimal hitting sets, a fundamental combinatorial problem, and provides a suite of implementations with a Docker-based interface for computational scientists to test on their own inputs.
Finding inclusion-minimal "hitting sets" for a given collection of sets is a fundamental combinatorial problem with applications in domains as diverse as Boolean algebra, computational biology, and data mining. Much of the algorithmic literature focuses on the problem of *recognizing* the collection of minimal hitting sets; however, in many of the applications, it is more important to *generate* these hitting sets. We survey twenty algorithms from across a variety of domains, considering their history, classification, useful features, and computational performance on a variety of synthetic and real-world inputs. We also provide a suite of implementations of these algorithms with a ready-to-use, platform-agnostic interface based on Docker containers and the AlgoRun framework, so that interested computational scientists can easily perform similar tests with inputs from their own research areas on their own computers or through a convenient Web interface.