Vertex cover in hypergraphs

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.