Vertex Cover - Vertex Cover in Hypergraphs

Vertex Cover in Hypergraphs

Given a collection of sets, a set which intersects all sets in the collection in at least one element is called a hitting set, and a simple NP-hard problem is to find a hitting set of smallest size or minimum hitting set. By mapping the sets in the collection onto hyperedges, this can be understood as a natural generalization of the vertex cover problem to hypergraphs which is often just called vertex cover for hypergraphs and, in a more combinatorial context, transversal. The notions of hitting set and set cover are equivalent.

Formally, let H = (V, E) be a hypergraph with vertex set V and hyperedge set E. Then a set SV is called hitting set of H if, for all edges eE, it holds Se ≠ ∅. The computational problems minimum hitting set and hitting set are defined as in the case of graphs. Note that we get back the case of vertex covers for simple graphs if the maximum size of the hyperedges is 2.

If that size is restricted to d, 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.

Read more about this topic:  Vertex Cover

Famous quotes containing the word cover:

    If I use the media, even with tricks, to publicise a black youth being shot in the back in Teaneck, New Jersey ... then I should be praised for it, and it’s more of a comment on them than me that it would take tricks to make them cover the loss of life.
    Al, Rev. Sharpton (b. 1954)