The minimal hitting set generation problem: algorithms and computation
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 2086380 (Why is no real title available?)
- A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
- A Lower Bound for the HBC Transversal Hypergraph Generation
- A Worst-Case Analysis of the Sequential Method to List the Minimal Hitting Sets of a Hypergraph
- A correction to the algorithm in Reiter's theory of diagnosis
- A data mining formalization to improve hypergraph minimal transversal computation
- A global parallel algorithm for the hypergraph transversal problem
- A theory of diagnosis from first principles
- A variant of Reiter's hitting-set algorithm
- An Efficient Algorithm for the Transversal Hypergraph Generation
- An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
- Complexity of identification and dualization of positive Boolean functions
- Computational aspects of monotone dualization: a brief survey
- Computing and Combinatorics
- Degrees of acyclicity for hypergraphs and relational database schemes
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
- Efficient algorithms for dualizing large-scale hypergraphs
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- Experimental comparison of the two Fredman-Khachiyan-algorithms
- Graph-Based Algorithms for Boolean Function Manipulation
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Left-to-right multiplication for monotone Boolean dualization
- Lower bounds for three algorithms for transversal hypergraph generation
- Minimal approximate hitting sets and rule templates
- Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
- Monotone Boolean functions
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- On generating all maximal independent sets
- On maximal frequent and minimal infrequent sets in binary matrices
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
- On the Desirability of Acyclic Database Schemes
- On the complexity of monotone dualization and generating minimal hypergraph transversals
- Optimizations for the Boolean approach to computing minimal hitting sets
- Reverse-engineering of polynomial dynamical systems
- Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
- Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden \(2 \times 2\) subgames
- The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
- The computation of hitting sets: Review and new algorithms
- There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
Cited in
(21)- Implementing efficient All solutions SAT solvers
- An approximation algorithm for the k-prize-collecting hitting set problem
- Compressed representation of learning spaces
- Enumerating minimal connected dominating sets
- Optimizations for the Boolean approach to computing minimal hitting sets
- Enumerating minimal connected dominating sets
- How many clues to give? A bilevel formulation for the minimum Sudoku clue problem
- The complexity of dependency detection and discovery in relational databases
- Explanations for query answers under existential rules
- Minimal Roman dominating functions: extensions and enumeration
- scientific article; zbMATH DE number 2040676 (Why is no real title available?)
- A Generic Program for Minimal Subsets with Applications
- Towards formal XAI: formally approximate minimal explanations of neural networks
- The computation of hitting sets: Review and new algorithms
- A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets
- Minimal winning coalitions and orders of criticality
- Compression with wildcards: all exact or all minimal hitting sets
- scientific article; zbMATH DE number 7286679 (Why is no real title available?)
- Minimal Roman dominating functions: extensions and enumeration
- Computing minimal hitting sets with a genetic algorithm
- An efficient branch-and-bound solver for hitting set
This page was built for publication: The minimal hitting set generation problem: algorithms and computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2953406)
