mhs-calculator: a minimal hitting sets calculator

mhs-calculator is a free, command line tool for the computation of minimal hitting sets (mhs) in hypergraphs. mhs-calculator provides two different algorithmic implementations: a modified Berge algorithm and an integer program formulation (see below for references). The latter requires an external linear programming solver. MHScalculator provides interfaces to

  • GLPK (open source)
  • Gurobi (commerical, but free academic license)
  • CPLEX (commerical, but free academic license)

If you use this software for your publications, please read and cite

MHScalculator can be redistributed and used in source form, with or without modification, provided agreeing to the Simplified BSD License.

We developed, tested, and used MHScalculator on MAC OS X and Linux Debian systems. MHScalculator will certainly also run on other Linux distributions. Note that Windows computers are not supported by MHScalculator.

  • Download and unzip and untar MHScalculator, e.g. tar -xzf 20131114_mhsCalculator_v1.1.<wbr></wbr>tar.gz
  • Change to the newly created MHScalculator directory
  • Read the provided README file

The MHScalculator requires an installed posix thread library libpthread (including header file glpk.h). In order to use MHScalculator's linear programming algorithm - at least - one of the following solvers must be installed (library and header files):

  • GLPK

If they cannot be found by make, the executables for the linear programming algorithms are not built! However, the Berge algorithm does not require any 'exotic' library and can be built anyway. In order to compile the executables, do the following:

  • Execute ./configure
  • Use ./configure's CFLAGS and LDFLAGS to tell make where to find the required header and library files
  • Execute make

For details and examples how to use CFLAGS and LDFLAGS see the provided README file.

The package contains several examples including start scripts to run these examples. Read the README file and have a look at the directory example for further details.