There is a classical algorithm for computing the transversal hypergraph described in Berge's Hypergraphs, Combinatorics of Finite Sets (North-Holland, Amsterdam, etc., 1989). The algorithm itself dates back much further and has been rediscovered for various applications. We provide here an implementation of a slightly modified version of this algorithm in MATLAB.

The modifications mainly consist of not generating unnecessary edges and not checking if certain edges are contained in certain other edges when that is necessarily not the case. While the worst-case complexity of this algorithm is not known (and not polynomial), it does appear to work well in practice. The main bottleneck is culling supersets from generated intermediate lists. For more details, please consult our paper (link) in which we investigate the use of this and other algorithms in an application to metabolic networks. Please let me know if you would like access to this paper.

MATLAB hypergraph transversal code

This code is copyrighted, but it is available for non-commercial use free of charge under the GNU General Public License.

---

This page maintained by Tamon Stephen. Last modified June 2nd, 2008.