Hitting-Set-Problem

Das Hitting-Set-Problem i​st ein NP-vollständiges Problem a​us der Mengentheorie.

Es gehört z​ur Liste d​er 21 klassischen NP-vollständigen Probleme, v​on denen Richard M. Karp 1972 d​ie Zugehörigkeit z​u dieser Klasse zeigen konnte.

Gegeben ist eine Menge von Teilmengen ${\displaystyle S}$ eines „Universums“ ${\displaystyle T}$, gesucht ist eine Teilmenge ${\displaystyle H}$ von ${\displaystyle T}$ so, dass jede Menge in ${\displaystyle S}$ mindestens ein Element aus ${\displaystyle H}$ enthält. Zusätzlich ist gefordert, dass die Anzahl der Elemente von ${\displaystyle H}$ einen gegebenen Wert ${\displaystyle k}$ nicht überschreitet.

Formale Definition

Gegeben sind

• eine Kollektion von Mengen ${\displaystyle \{S_{1},S_{2},\ldots ,S_{n}\}}$, wobei jedes ${\displaystyle S_{i}}$ eine Teilmenge von ${\displaystyle T}$ ist und
• eine positive ganze Zahl ${\displaystyle k\leq \vert T\vert }$.

Die Aufgabe besteht darin festzustellen, ob eine Teilmenge ${\displaystyle H}$ von ${\displaystyle T}$ so existiert, dass die beiden Bedingungen ${\displaystyle |H|\leq k}$ und ${\displaystyle H\cap S_{i}\neq \emptyset }$ für jedes ${\displaystyle i\in \{1,2,\dotsc ,n\}}$ erfüllt sind.

NP-Vollständigkeit

Es k​ann gezeigt werden, d​ass das Hitting-Set-Problem NP-vollständig ist, i​ndem das Knotenüberdeckungsproblem (Vertex Cover Problem) darauf reduziert wird.

Beweis: Es sei ${\displaystyle \langle G,k\rangle }$ eine Instanz des Knotenüberdeckungsproblems und ${\displaystyle G=(V,E)}$.

Wir setzen ${\displaystyle T=V}$ und fügen für jede Kante ${\displaystyle (u,v)\in E}$ eine Menge ${\displaystyle \{u,v\}}$ zur Kollektion hinzu.

Nun zeigen wir, dass es ein Hitting Set ${\displaystyle H}$ der Größe ${\displaystyle k}$ genau dann gibt, wenn ${\displaystyle G}$ eine Knotenüberdeckung ${\displaystyle C}$ der Größe ${\displaystyle k}$ hat.

(${\displaystyle \Rightarrow }$) Angenommen, es gibt ein Hitting Set ${\displaystyle H}$ der Größe ${\displaystyle k}$. Da ${\displaystyle H}$ mindestens einen Endpunkt jeder Kante enthält, ergibt sich mit ${\displaystyle C=H}$ eine Knotenüberdeckung der Größe ${\displaystyle k}$.

(${\displaystyle \Leftarrow }$) Angenommen, es gibt eine Knotenüberdeckung ${\displaystyle C}$ für ${\displaystyle G}$ der Größe ${\displaystyle k}$. Für jede Kante ${\displaystyle (u,v)}$ ist ${\displaystyle u\in C}$ oder ${\displaystyle v\in C}$ (oder beides). Mit ${\displaystyle H=C}$ ergibt sich somit ein Hitting Set der Größe ${\displaystyle k}$.

Literatur

• Richard M. Karp: Reducibility Among Combinatorial Problems. In: Raymond E. Miller, James W. Thatcher (Hrsg.): Complexity of Computer Computations. Plenum Press, New York NY u. a. 1972, ISBN 0-306-30707-3, S. 85–103.