Heim

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 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 Zahl der Elemente von H einen gegebenen Wert K nicht überschreitet.

Formale Definition

Gegeben:

Die Aufgabe besteht darin, festzustellen, ob eine Teilmenge H von T existiert, sodass

.

NP-Vollständigkeit

Es kann gezeigt werden, dass das Hitting Set Problem NP-vollständig ist, indem es auf das Knotenüberdeckungsproblem zurückgeführt wird.

Beweis

Es sei <G, k> eine Instanz des Knotenüberdeckungsproblems (Vertex Cover Problem) und G = (V, E). Es sei T = V und (u, v) E wird eine neue Menge {u,v} der Kollektion hinzugefügt. Dann zeigen wir, dass es ein Hitting Set H der Grösse k genau dann gibt, wenn G eine Knotenüberdeckung C der Größe k hat.

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

() Angenommen, es gibt eine Knotenüberdeckung C für G der Grösse k. Für jede Kante (u,v) ist entweder u C oder v C. Mit C := H ergibt sich ein Hitting Set der Grösse k.