Problem der exakten Überdeckung

Das Problem d​er exakten Überdeckung (englisch Exact Cover) i​st ein Entscheidungsproblem d​er Kombinatorik. Es gehört z​u den 21 klassischen NP-vollständigen Problemen, v​on denen Richard M. Karp 1972 gezeigt hat, d​ass sie NP-vollständig sind.

Gegeben sind eine Menge ${\displaystyle X}$ und eine Menge ${\displaystyle S}$ von nichtleeren Teilmengen von ${\displaystyle X}$, also ${\displaystyle S\subseteq {\mathcal {P}}(X)}$, wobei ${\displaystyle {\mathcal {P}}(X)}$ die Potenzmenge von ${\displaystyle X}$ bezeichnet.

Gesucht ist eine Teilmenge ${\displaystyle U}$ von ${\displaystyle S}$, deren disjunkte Vereinigung ${\displaystyle X}$ ist:

${\displaystyle X={\dot {\bigcup _{Y\in U}}}Y}$.

Das heißt: Jedes Element in ${\displaystyle X}$ soll in genau einer der Mengen in ${\displaystyle U}$ vorkommen. Die Mengen in ${\displaystyle U}$ bilden also eine exakte Überdeckung von ${\displaystyle X}$ (${\displaystyle U}$ ist eine Partition von ${\displaystyle X}$).

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

Zum Beispiel sei

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

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

Die Menge

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

zeigt, d​ass eine exakte Überdeckung existiert.

Siehe auch

• Mengenzerlegungsproblem