3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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:

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.

$\endgroup$
  • $\begingroup$ Thank you for the answer and the reference. I am not a C++ expert so it will probably take me some time to figure it out, but it looks promising! $\endgroup$ – Pjotr5 Jul 13 '18 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.