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 ${\displaystyle S}${\displaystyle S} eines „Universums" ${\displaystyle T}${\displaystyle T}, gesucht ist eine Teilmenge ${\displaystyle H}${\displaystyle H} von ${\displaystyle T}${\displaystyle T} so, dass jede Menge in ${\displaystyle S}${\displaystyle S} mindestens ein Element aus ${\displaystyle H}${\displaystyle H} enthält. Zusätzlich ist gefordert, dass die Anzahl der Elemente von ${\displaystyle H}${\displaystyle H} einen gegebenen Wert ${\displaystyle k}${\displaystyle k} nicht überschreitet.

Gegeben sind

• eine Kollektion von Mengen ${\displaystyle \{S_{1},S_{2},\ldots ,S_{n}\}}${\displaystyle \{S_{1},S_{2},\ldots ,S_{n}\}}, wobei jedes ${\displaystyle S_{i}}${\displaystyle S_{i}} eine Teilmenge von ${\displaystyle T}${\displaystyle T} ist und
• eine positive ganze Zahl ${\displaystyle k\leq \vert T\vert }${\displaystyle k\leq \vert T\vert }.

Die Aufgabe besteht darin festzustellen, ob eine Teilmenge ${\displaystyle H}${\displaystyle H} von ${\displaystyle T}${\displaystyle T} so existiert, dass die beiden Bedingungen ${\displaystyle |H|\leq k}${\displaystyle |H|\leq k} und ${\displaystyle H\cap S_{i}\neq \emptyset }${\displaystyle H\cap S_{i}\neq \emptyset } für jedes ${\displaystyle i\in \{1,2,\dotsc ,n\}}${\displaystyle i\in \{1,2,\dotsc ,n\}} erfüllt sind.

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

Beweis: Es sei ${\displaystyle \langle G,k\rangle }${\displaystyle \langle G,k\rangle } eine Instanz des Knotenüberdeckungsproblems und ${\displaystyle G=(V,E)}${\displaystyle G=(V,E)}.

Wir setzen ${\displaystyle T=V}${\displaystyle T=V} und fügen für jede Kante ${\displaystyle (u,v)\in E}${\displaystyle (u,v)\in E} eine Menge ${\displaystyle \{u,v\}}${\displaystyle \{u,v\}} zur Kollektion hinzu.

Nun zeigen wir, dass es ein Hitting Set ${\displaystyle H}${\displaystyle H} der Größe ${\displaystyle k}${\displaystyle k} genau dann gibt, wenn ${\displaystyle G}${\displaystyle G} eine Knotenüberdeckung ${\displaystyle C}${\displaystyle C} der Größe ${\displaystyle k}${\displaystyle k} hat.

(${\displaystyle \Rightarrow }${\displaystyle \Rightarrow }) Angenommen, es gibt ein Hitting Set ${\displaystyle H}${\displaystyle H} der Größe ${\displaystyle k}${\displaystyle k}. Da ${\displaystyle H}${\displaystyle H} mindestens einen Endpunkt jeder Kante enthält, ergibt sich mit ${\displaystyle C=H}${\displaystyle C=H} eine Knotenüberdeckung der Größe ${\displaystyle k}${\displaystyle k}.

(${\displaystyle \Leftarrow }${\displaystyle \Leftarrow }) Angenommen, es gibt eine Knotenüberdeckung ${\displaystyle C}${\displaystyle C} für ${\displaystyle G}${\displaystyle G} der Größe ${\displaystyle k}${\displaystyle k}. Für jede Kante ${\displaystyle (u,v)}${\displaystyle (u,v)} ist ${\displaystyle u\in C}${\displaystyle u\in C} oder ${\displaystyle v\in C}${\displaystyle v\in C} (oder beides). Mit ${\displaystyle H=C}${\displaystyle H=C} ergibt sich somit ein Hitting Set der Größe ${\displaystyle k}${\displaystyle k}.

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

• Komplexitätstheorie
• Mengenlehre