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 . ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle H}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle k}$

Formal definition

Given are

• a collection of sets , each being a subset of and ${\displaystyle \{S_{1},S_{2},\ldots ,S_{n}\}}$ ${\displaystyle S_{i}}$ ${\displaystyle T}$
• a positive integer . ${\displaystyle k\leq \vert T\vert }$

The task is to determine whether a subset of exists such that the two conditions and are met for each . ${\displaystyle H}$ ${\displaystyle T}$ ${\displaystyle |H|\leq k}$ ${\displaystyle H\cap S_{i}\neq \emptyset }$ ${\displaystyle i\in \{1,2,\dotsc ,n\}}$

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 . ${\displaystyle \langle G,k\rangle }$ ${\displaystyle G=(V,E)}$

We put and add a lot to the collection for each edge . ${\displaystyle T=V}$ ${\displaystyle (u,v)\in E}$ ${\displaystyle \{u,v\}}$

Now we show that there is a hitting set of size if and only if a node cover has the size . ${\displaystyle H}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle C}$ ${\displaystyle k}$

( ) 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 . ${\displaystyle \Rightarrow }$ ${\displaystyle H}$ ${\displaystyle k}$ ${\displaystyle H}$ ${\displaystyle C=H}$ ${\displaystyle k}$

( ) 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 . ${\displaystyle \Leftarrow }$ ${\displaystyle C}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle (u,v)}$ ${\displaystyle u\in C}$ ${\displaystyle v\in C}$ ${\displaystyle H=C}$ ${\displaystyle k}$

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.