Hitting-Set-Problem

Das Hitting-Set-Problem ist ein NP-vollständiges Problem aus der Mengentheorie.

Es gehört zur Liste der 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ä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.

{{safesubst:#ifeq:0|10| {{#switch: Hitting-Set-Problem |Navigationsleiste|NaviBlock|0=|#default= Vorlage:Templatetransclusioncheck Vorlage:Dokumentation/ruler }}}}Vorlage:Klappleiste/Anfang {{#if:

|

Erfüllbarkeitsproblem der Aussagenlogik | Cliquenproblem | Mengenpackungsproblem | Knotenüberdeckungsproblem | Mengenüberdeckungsproblem | Feedback Arc Set | Feedback Vertex Set | Hamiltonkreisproblem | Integer Linear Programming | 3-SAT | graph coloring problem | Covering by cliques | Problem der exakten Überdeckung | 3-dimensional matching | Steinerbaumproblem | Hitting set | Rucksackproblem | Job sequencing | Partitionsproblem | Maximaler Schnitt }} Vorlage:Klappleiste/Ende

en:Hitting set problem