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

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,\dots ,S_n\}$, wobei jedes $S_i$ eine Teilmenge von $T$ ist und
• eine positive ganze Zahl $k\le |T|$.

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 \mathrm{\varnothing }$ für jedes $i\in \{1,2,\dots ,n\}$ erfüllt sind.

NP-Vollständigkeit

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

Beweis: Es sei $⟨G,k⟩$ 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: 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.