Hitting-Set-Problem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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-Schwere[Bearbeiten]

Es kann gezeigt werden, dass das Hitting-Set-Problem NP-schwer 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[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.