Problem der exakten Überdeckung

Das Problem der exakten Überdeckung (englisch Exact Cover) ist ein Entscheidungsproblem der Kombinatorik. Es gehört zu den 21 klassischen NP-vollständigen Problemen, von denen Richard M. Karp 1972 gezeigt hat, dass sie NP-vollständig sind.

Gegeben ist eine Menge $X$ und eine Menge $S$, die Teilmengen von $X$ enthält, also $S \subseteq \mathcal{P}(X)$, wobei $\mathcal{P}(X)$ die Potenzmenge von $X$ bezeichnet.

Gesucht ist eine Teilmenge $U$ von $S$, deren Disjunkte Vereinigung $X$ ist:

$X = \dot{\bigcup_{X_i\in U}}X_i$.

D. h. jedes Element in $X$ soll in genau einer der Mengen in $U$ vorkommen. Die Mengen in $U$ bilden also eine exakte Überdeckung von $X$.

Grafische Darstellung des Beispiels (die exakte Überdeckung ist rot eingezeichnet)

Zum Beispiel sei

$X = \{a, b, c, d, e, f\}$ und

$S = \{ \{a,b\}, \{a,b,c\}, \{c, e\}, \{d, f\}, \{e, f\} \}$.

Die Menge

$U = \{ \{a,b\}, \{c, e\}, \{d, f\} \}$

zeigt, dass eine exakte Überdeckung existiert.

Siehe auch

• Mengenzerlegungsproblem

Karps 21 NP-vollständige Probleme

Erfüllbarkeitsproblem der Aussagenlogik | Cliquenproblem | Mengenpackungsproblem | Knotenüberdeckungsproblem | Mengenüberdeckungsproblem | Feedback Arc Set | Feedback Vertex Set | Hamiltonkreisproblem | Integer Linear Programming | 3-SAT | graph coloring problem | Covering by cliques | Problem der exakten Überdeckung | 3-dimensional matching | Steinerbaumproblem | Hitting set | Rucksackproblem | Job sequencing | Partitionsproblem | Maximaler Schnitt