Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Vertex cover in hypergraphs
Summary
In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph.
An equivalent term is a hitting set: given a collection of sets, a set which intersects all sets in the collection in at least one element is called a hitting set. The equivalence can be seen by mapping the sets in the collection onto hyperedges.
Another equivalent term, used more in a combinatorial context, is transversal.
The notions of hitting set and set cover are equivalent too.
Recall that a hypergraph H is a pair (V, E), where V is a set of vertices and E is a set of subsets of V called hyperedges. Each hyperedge may contain one or more vertices.
A vertex-cover (aka hitting set or transversal) in H is set T ⊆ V such that, for all hyperedges e ∈ E, it holds that T ∩ e ≠ ∅.
The vertex-cover number (aka transversal number) of a hypergraph H is the smallest size of a vertex cover in H. It is often denoted by τ(H).
For example, if H is this 3-uniform hypergraph:
{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }
then H has admits several vertex-covers of size 2, for example:
{1, 6}
However, no subset of size 1 hits all the hyperedges of H. Hence the vertex-cover number of H is 2.
Note that we get back the case of vertex covers for simple graphs if the maximum size of the hyperedges is 2.
The computational problems minimum hitting set and hitting set are defined as in the case of graphs.
If the maximum size of a hyperedge is restricted to d, then the problem of finding a minimum d-hitting set permits a d-approximation algorithm. Assuming the unique games conjecture, this is the best constant-factor algorithm that is possible and otherwise there is the possibility of improving the approximation to d − 1.
For the hitting set problem, different parametrizations make sense. The hitting set problem is W[2]-complete for the parameter OPT, that is, it is unlikely that there is an algorithm that runs in time f (OPT)n^O^(1) where OPT is the cardinality of the smallest hitting set.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.