Ein Hitting Set ist eine Teilmenge H einer Grundmenge U, die jede gegebene Teilmenge S₁, S₂, …, S_m von U mindestens einmal schneidet – für jedes i gilt also H ∩ S_i ≠ ∅. Gesucht ist ein möglichst kleines H. Das Entscheidungsproblem (gibt es ein Hitting Set der Größe ≤ k?) ist NP-vollständig.
Beispiel: Kameraüberwachung
Eine Lagerhalle hat mehrere Zonen; jede Zone ist eine Menge von möglichen Kamerapositionen. Gesucht ist die kleinste Menge an Positionen, sodass jede Zone von mindestens einer Kamera abgedeckt wird. Genau das ist ein Hitting Set: Jede Zone (Teilmenge) muss einen Treffer (Kamera) enthalten.
Verwandtschaft: Set Cover und Vertex Cover
Hitting Set ist das duale Problem zum Set Cover: Vertauscht man die Rollen von Elementen und Mengen, entsteht aus jedem Hitting Set ein Set Cover und umgekehrt. Ein wichtiger Spezialfall ist das Vertex Cover: Betrachtet man jede Kante als zweielementige Menge ihrer Endknoten, dann ist ein Hitting Set genau eine Knotenüberdeckung.
Algorithmen
- Ein Greedy-Algorithmus wählt wiederholt das Element, das die meisten noch nicht getroffenen Mengen schneidet – er erreicht wie beim Set Cover eine Güte von höchstens ln(n) relativ zum Optimum.
- Für kleine Parameter k lässt sich das Problem mit Fix-Parameter-Algorithmen (FPT) lösen.
- Genauere Garantien liefern Approximationsalgorithmen, für Spezialfälle gibt es exakte polynomiale Verfahren.
Anwendungen
- Testauswahl: kleinste Menge von Testfällen, die alle Anforderungen abdeckt
- Sensor- und Kameraplatzierung: jede Zone wird überwacht
- Fehlerdiagnose: kleinste Menge von Messpunkten, die jede Fehlerquelle erkennt
Einordnung: Wie das Set Cover gehört das Hitting Set zur Familie der NP-vollständigen Probleme – kleine Instanzen lassen sich per Branch-and-Bound, große nur heuristisch lösen.