Hitting set problem
The hitting set problem is an NP-complete problem from set theory.
It belongs to the list of the 21 classic NP-complete problems , of which Richard M. Karp was able to show that they belong to this class in 1972.
Given is a set of subsets of a "universe" , a subset of is sought such that each set contains at least one element from . In addition, it is required that the number of elements does not exceed a given value .
Formal definition
Given are
- a collection of sets , each being a subset of and
- a positive integer .
The task is to determine whether a subset of exists such that the two conditions and are met for each .
NP completeness
It can be shown that the hitting set problem is NP-complete is by the vertex cover (vertex cover problem) is reduced to.
Proof : Let it be an instance of the vertex coverage problem and .
We put and add a lot to the collection for each edge .
Now we show that there is a hitting set of size if and only if a node cover has the size .
( ) Suppose there is a hitting set of size . Since each edge contains at least one end point, there is a node overlap of the size .
( ) Suppose there is a node coverage for the size . For each edge is or (or both). With this results in a hitting set of the size .
literature
- Richard M. Karp : Reducibility Among Combinatorial Problems. In: Raymond E. Miller, James W. Thatcher (Eds.): Complexity of Computer Computations. Plenum Press, New York NY et al. 1972, ISBN 0-306-30707-3 , pp. 85-103.