Vertex cover#Vertex cover in hypergraphs

The Hitting Set problem is an NP -complete problem in set theory.

It belongs to the list of 21 classic NP -complete problems, of which Richard M. Karp 1972 could show the belonging to this class.

Given a set of subsets S of a " universe " T sought is a subset H of T such that each set in S contains at least one element of H. In addition, it is required that the number of elements of H does not exceed a given value of k.

Formal definition

Are given

• A collection of sets, each of which is a subset of and
• Is a positive integer.

The task is to determine whether a subset of so exists that the two conditions and for each are met.

NP- completeness

It can be shown that the Hitting Set problem is NP-complete by the vertex cover problem ( vertex cover problem) is reduced to it.

Proof: Let an instance of the vertex cover problem and.

We set and add for each edge a lot to library.

Now we show that there are exactly k then outputs a hitting set H of size, if G has a vertex cover C of size k.

() Suppose there is a Hitting Set H of size k, since H contains at least one endpoint of each edge, resulting with C = H is a vertex cover of size k

() Suppose there is a vertex cover C for G of size k for each edge or ( or both). With H = C, thus a hitting set of size k yields