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.

Ein alltägliches Beispiel

Für ein Projekt soll ein Team zusammengestellt werden. In dem Team sollen Kompetenzen auf den Gebieten Architektur, Bauphysik, Chemie, Datenverarbeitung, Elektrotechnik und Finanzierung vertreten sein. Dabei kann ein Teammitglied mehrere Kompetenzen mitbringen. Außerdem soll keine Kompetenz mehrfach vertreten sein, denn das wäre eine Vergeudung von Humanressourcen. Zur Verfügung stehen folgende fünf Personen:

Anna ist kompetent für Architektur und Bauphysik, Boris für Architektur, Bauphysik und Chemie, Charlotte für Chemie und Elektrotechnik, Dennis für Datenverarbeitung und Finanzierung, Emma für Elektrotechnik und Finanzierung. Wie soll das Team nun aussehen? Wenn man Boris nimmt, scheidet Charlotte für die Abdeckung der Elektrotechnik aus, da dann die Chemie doppelt vertreten wäre. Also muss man zur Abdeckung der Elektrotechnik Emma heranziehen, was wegen der Finanzierung Dennis ausschließt, so dass die Datenverarbeitung nicht mehr abgedeckt werden kann. Also kann man von Anfang an Boris nicht verwenden. Das Problem ist aber lösbar, indem man das Team aus Anna, Charlotte und Dennis bildet. Das ist die so genannte exakte Überdeckung, hier von Teamkompetenzen durch Teammitglieder.

Es ist kein Zufall, dass die Argumentationsweise an das Sudoku-Lösen erinnert. Auch Sudoku ist ein Exact-cover-Problem.

Mathematische Formulierung

Gegeben sind eine Menge $X$ und eine Menge $S$ von nichtleeren Teilmengen von $X$ , 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 _{Y\in U}}}Y

.

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