Mengenüberdeckungsproblem

Das Mengenüberdeckungsproblem (oft mit set-covering-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik.

Es fragt, ob zu einer Menge ${\displaystyle U}$ und ${\displaystyle n}$ Teilmengen ${\displaystyle S_{j}}$ von ${\displaystyle U}$ und einer natürlichen Zahl ${\displaystyle k\leq n}$ eine Vereinigung von ${\displaystyle k}$ oder weniger Teilmengen ${\displaystyle S_{j}}$ existiert, die der Menge ${\displaystyle U}$ entspricht (Überdeckung).

Als Optimierungsproblem formuliert, wird eine Überdeckung mit möglichst kleiner Anzahl der Teilmengen ${\displaystyle S_{j}}$ gesucht oder, falls den Teilmengen ${\displaystyle S_{j}}$ Kosten ${\displaystyle c_{j}}$ zugeordnet sind, eine Überdeckung mit geringsten Kosten.

Das Mengenüberdeckungsproblem gehört zur Liste der 21 klassischen NP-vollständigen Probleme, von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.

Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein: Algorithmen – Eine Einführung. Walter de Gruyter, 2017, ISBN 9783110522013, S. 1128–1133