Quelltext der Seite Hitting-Set-Problem

Das '''Hitting-Set-Problem''' ist ein [[NP-vollständig]]es Problem aus der Mengentheorie.

Es gehört zur Liste der [[Karps 21 NP-vollständige Probleme|21 klassischen NP-vollständigen Probleme]], von denen [[Richard M. Karp]] 1972 die Zugehörigkeit zu dieser Klasse zeigte.

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

== Formale Definition ==
Gegeben sind
* eine Kollektion von Mengen <math>\{ S_1, S_2,\ldots , S_n \}</math>, wobei jedes <math>S_i </math> eine Teilmenge von <math>T</math> ist und
* eine positive ganze Zahl <math>k \leq \vert T \vert </math>.
Die Aufgabe besteht darin festzustellen, ob eine Teilmenge <math>H</math> von <math>T</math> so existiert, dass die beiden Bedingungen <math>|H| \le k</math> und <math>H \cap S_i \ne \emptyset</math> für jedes <math>i\in\{1,2,\dotsc, n\}</math> erfüllt sind.

== NP-Vollständigkeit ==
Das Hitting-Set-Problem ist [[NP-Vollständigkeit|NP-vollständig]], da das [[Knotenüberdeckungsproblem]] (Vertex Cover Problem) darauf reduzierbar ist.

'''Beweis''':
Es sei <math>\langle G,k \rangle</math> eine Instanz des Knotenüberdeckungsproblems und <math> G = (V, E)</math>.

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

Nun zeigen wir, dass es ein Hitting Set <math>H</math> der Größe <math>k</math> genau dann gibt, wenn <math>G</math> eine Knotenüberdeckung <math>C</math> der Größe <math>k</math> hat.

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

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

== 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.

{{Navigationsleiste Karps 21 NP-vollständige Probleme}}

[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Mengenlehre]]

[[en:Hitting set problem]]