The repository includes a large collection of algorithm implementations. We give a references and a few details for each here. For full details, see our paper.
The listing below is sorted taxonomically, rather than according to which container provides each algorithm; information about the containers can be found in their respective directories.
Some of these algorithms support 'cutoff' enumeration—that is, searching for MHSes of size no larger than some specified bound.
(Supports cutoff) A sequential algorithm based on an algebraic decomposition of the input hypergraph. First published in 1984 by Berge in Hypergraphs: combinatorics of finite sets.
An implementation in C++ by A. Gainer-Dewar is provided in the compsysmed/agdmhs container in the agdmhs directory.
You can run this container online on the Algorun server.
(Supports cutoff) A corrected version of Reiter's algorithm, published in A correction to the algorithm in Reiter's theory of diagnosis by Greiner, Smith, and Wilkerson. An implementation in Python by T. Quaritsch and I. Pill is available as part of PyMBD, which is distributed as a zip bundle from Pill's website.
The implementation is provided in the compsysmed/pymbd container in the pymbd directory under the terms of the authors' license.
You can run this container online on the Algorun server.
(Supports cutoff) A corrected version of Reiter's algorithm, published in A variant of Reiter's hitting-set algorithm by Wotawa. An implementation in Python by T. Quaritsch and I. Pill is available as part of PyMBD, which is distributed as a zip bundle from Pill's website.
The implementation is provided in the compsysmed/pymbd container in the pymbd directory under the terms of the authors' license.
You can run this container online on the Algorun server.
An improved Berge's algorithm published in A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns.
An implementation in C by K. Murakami is available from the Hypergraph Dualization Repository and is provided in the compsysmed/bmr container in the bmr directory by permission from the authors.
You can run this container online on the Algorun server.
An improved Berge's algorithm published in Mining border descriptions of emerging patterns from dataset pairs by Dong and Li.
An implementation in C by K. Murakami is available from the Hypergraph Dualization Repository and is provided in the compsysmed/dl container in the dl directory by permission from the authors.
You can run this container online on the Algorun server.
A variation of Berge's algorithm which searches depth first and thus avoids the need to store large intermediate hypergraphs in memory. Published in An efficient algorithm for the transversal hypergraph generation by Kavvadias and Stavroupoulos.
A Pascal implementation by D. Kavvadias and E. Stavropoulos is available from the Hypergraph Dualization Repository and the author's page and is provided in the compsysmed/ks container in the ks directory by permission from the authors.
You can run this container online on the Algorun server.
The A algorithm from On the complexity of dualization of monotone disjunctive normal forms, Fredman, M. and Khachiyan, L, as improved in An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation, E. Boros et al. Has the best known asymptotic bounds on runtime of any serial algorithm with a public implementation.
An implementation in compiled C is available from the Hypergraph Dualization Repository and is provided in the compsysmed/fka-begk container in the fka-begk directory by permission from the authors.
You can run this container online on the Algorun server.
An implementation in C++ of the original, unmodified algorithm is provided in the compsysmed/agdmhs container in the agdmhs directory.
You can run this container online on the Algorun server.
(Supports cutoff) A divide-and-conquer algorithm introduced in The computation of hitting sets: review and new algorithms by Lin and Jiang. An implementation in Python by T. Quaritsch and I. Pill is available as part of PyMBD, which is distributed as a zip bundle from Pill's website.
The implementation is provided in the compsysmed/pymbd container in the pymbd directory under the terms of the authors' license.
You can run this container online on the Algorun server.
(Supports cutoff) A divide-and-conquer approximation algorithm, published in A low-cost approximate minimal hitting set algorithm and its application to model-based diagnosis (PDF) by Abreu and Gemund. An implementation in Python by T. Quaritsch and I. Pill is available as part of PyMBD, which is distributed as a zip bundle from Pill's website.
The implementation is provided in the compsysmed/pymbd container in the pymbd directory under the terms of the authors' license.
You can run this container online on the Algorun server.
A parallel algorithm using a Berge-like calculation on divided subhypergraphs, published in Parallel computation of the minimal elements of a poset by Leiserson et al. An implementation in Cilk++ by those authors is available from the BPASlib project's webpage.
The implementation is provided in the compsysmed/partran container in the partran directory under the terms of the authors' license.
You can run this container online on the Algorun server.
An algorithm based on ZDD representations of hypergraphs or boolean functions. Introduced as solution to exercise 237 of §7.1.4 of Volume 4a of The Art of Computer Programming (1st ed.) by Donald E. Knuth.
An implementation in C by the author of Hypergraph transversal computation with binary decision diagrams is available from his website and is provided in the compsysmed/htcbdd container under the terms of the GPLv3 license.
This container is not hosted on the AlgoRun server due to resource constraints.
An improved version of KNUTH which uses both BDDs and ZDDs.
Introduced in Hypergraph transversal computation with binary decision diagrams by Takahesi Toda.
An implementation in C by Toda is available from his website and is provided in the compsysmed/htcbdd container under the terms of the GPLv3 license.
This container is not hosted on the AlgoRun server due to resource constraints.
(Supports cutoff) A parallel algorithm from An efficient distributed algorithm for computing minimal hitting sets (PDF) by Cardoso and Abreu.
An implementation in C++ by those authors is available from their GitHub repository and is provided in the compsysmed/mhs2 container in the mhs2 directory under the terms of the GPLv2 license.
You can run this container online on the Algorun server.
(Supports cutoff) A vertex-wise algorithm inspired by ideas from data mining and published in A data mining formalization to improve hypergraph minimal transversal computation (PDF) by Hébert, Bretto, and Crémilleux.
An implementation in C++, written by C. Hébert and now maintained by F. Rioult, is available as MtMiner and is provided in the compsysmed/hbc container in the hbc directory by permission from the authors.
You can run this container online on the Algorun server.
(Supports cutoff)
A vertex-wise "greedy" algorithm published in OCSANA: optimal combinations of interventions from network analysis.
An implementation in Java by M. Kordi, originally written for a refactoring of OCSANA, is provided in the compsysmed/ocsana container in the ocsana directory.
WARNING: Testing has revealed that this software does not accurately generate all MHSes. Accordingly, this container is not hosted on the AlgoRun server.
(pMMCS supports cutoff) Highly performant algorithm published in Efficient algorithms for dualizing large-scale hypergraphs in 2014 by Murakami and Uno.
Those authors provide a C implementation at the Hypergraph Dualization Repository, which is redistributed here in the in the compsysmed/shd container in the shd directory bypermission from the authors.
You can run this container online on the Algorun server.
An implementation in C++ which takes advantage of multiple cores using OpenMP is provided in the compsysmed/agdmhs container in the agdmhs directory.
You can run this container online on the Algorun server.
(pRS supports cutoff) Highly performant algorithm published in Efficient algorithms for dualizing large-scale hypergraphs in 2014 by Murakami and Uno.
Those authors provide a C implementation at the Hypergraph Dualization Repository, which is redistributed here in the in the compsysmed/shd container in the shd directory bypermission from the authors.
You can run this container online on the Algorun server.
An implementation in C++ which takes advantage of multiple cores using OpenMP is provided in the compsysmed/agdmhs container in the agdmhs directory.
You can run this container online on the Algorun server.
A "global parallel" algorithm based on a full cover decomposition of the input hypergraph. Published in A fast and simple parallel algorithm for the monotone duality problem by E. Boros and K. Makino.
An implementation in C++ using OpenMP by A. Gainer-Dewar is provided in the compsysmed/agdmhs container in the agdmhs directory.
You can run this container online on the Algorun server.
A method based on computational algebra.
An implementation in Python and Macaulay2 is provided in the compsysmed/primdecomp container in the primdecomp directory.
You can run this container online on the Algorun server.