Problem der exakten Überdeckung

Entscheidungsproblem der Kombinatorik

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

Bearbeiten

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

Bearbeiten

Gegeben sind eine Menge   und eine Menge   von nichtleeren Teilmengen von  , also  , wobei   die Potenzmenge von   bezeichnet.

Gesucht ist eine Teilmenge   von  , deren disjunkte Vereinigung   ist:

 .

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

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

Zum Beispiel sei

  und
 .

Die Menge

 

zeigt, dass eine exakte Überdeckung existiert.

Dieses Beispiel entspricht genau dem oben genannten alltäglichen Beispiel.

Siehe auch

Bearbeiten