Hitting-Set-Problem

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 eines „Universums“ , gesucht ist eine Teilmenge von so, dass jede Menge in mindestens ein Element aus enthält. Zusätzlich ist gefordert, dass die Anzahl der Elemente von einen gegebenen Wert nicht überschreitet.

Formale Definition[Bearbeiten | Quelltext bearbeiten]

Gegeben sind

  • eine Kollektion von Mengen , wobei jedes eine Teilmenge von ist und
  • eine positive ganze Zahl .

Die Aufgabe besteht darin festzustellen, ob eine Teilmenge von so existiert, dass die beiden Bedingungen und für jedes erfüllt sind.

NP-Vollständigkeit[Bearbeiten | Quelltext bearbeiten]

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 eine Instanz des Knotenüberdeckungsproblems und .

Wir setzen und fügen für jede Kante eine Menge zur Kollektion hinzu.

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

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

() Angenommen, es gibt eine Knotenüberdeckung für der Größe . Für jede Kante ist oder (oder beides). Mit ergibt sich somit ein Hitting Set der Größe .

Literatur[Bearbeiten | Quelltext bearbeiten]

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