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.

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.

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 .

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