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. mhs-calculator provides interfaces to:

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



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


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

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

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



The mhs-calculator requires an installed posix thread library libpthread (including header file glpk.h). In order to use mhs-calculator'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 of 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.