Software for finding a minimum vertex cover for a hypergraph

Question

A hypergraph $H = (V,E)$ consists of a finite set of vertices, say $V=\{1, \dots, n\}$ and a set of hyperedges $E \subseteq \mathcal{P}(V)$. We call $H$ a $k$-hypergraph if all $|e| = k$ for all $e\in E$. A vertex cover for $H$ is a set $V' \subseteq V$ such that for all $e \in E$ there is some $v \in V'$ such that $v \in e$. The problem I wish to solve computationally is finding a vertex cover of minimal size (a minimum vertex cover) for certain $k$-hypergraphs with $k>2$.

Is there any software (e.g a Python package) that can solve this problem given a $k$-hypergraph $H$? For normal graphs (2-hypergraphs), Mathematica has the function FindVertexCover, but it does not seem to have support for hypergraphs with higher cardinality edges. I could write my own program to solve this, but, since the problem of finding a minimum vertex cover is hard, I would prefer it if anyone could find something where most of the currently known optimization is already implemented.

Answer 1

I usually use SageMath for research work connected with graphs. However, I was not able to find there a ready-made algorithm to find a minimum vertex cover for a hypergraph (see subsection with the corresponding name).

Anyway, using Sage together with Python should simplify your life a lot as it will give access to a lot of convenient and tested data structures and algorithms for graph theory.

Now, regarding the vertex cover. I stumbled upon the following publicly available Ph.D. thesis:

• A. Aabrandt, "Algebraic varieties and system design," Ph.D. Thesis, Dept. Electr. Comput. Eng., Tech. Univ. Denmark, 2016..

There, in Appendix D, the author has the code (Python+Sage generated by C++) for vertex cover calculation, that should handle hypergraphs (as it is formulated as a cover ideal, see Section 6.1 "Edge and Cover Ideals for Hypergraphs"). I haven't used that code myself, but this is the best I have the knowledge about so far.