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 zeigen konnte.

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

Formale Definition

Gegeben sind

• eine Kollektion von Mengen $\{ S_1, S_2,\ldots , S_n \}$, wobei jedes S_i eine Teilmenge von T ist und
• eine positive ganze Zahl $k \leq \vert T \vert$.

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

NP-Vollständigkeit

Es kann gezeigt werden, dass das Hitting-Set-Problem NP-vollständig ist, indem das Knotenüberdeckungsproblem (Vertex Cover Problem) darauf reduziert wird.

Beweis

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

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

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

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

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

Literatur

• Richard M. Karp: Reducibility Among Combinatorial Problems. In: R. E. Miller, J. W. Thatcher (Hrsg.): Complexity of Computer Computations. Plenum Press, New York 1972, S. 85–103.

Karps 21 NP-vollständige Probleme

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