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

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

Das Hitting-Set-Problem ist NP-vollständig, da das Knotenüberdeckungsproblem (Vertex Cover Problem) darauf reduzierbar ist.

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