Exakte Überdeckung (englisch Exact Cover) ist ein Entscheidungsproblem der Kombinatorik: Gegeben sind eine Grundmenge U und eine Familie von Teilmengen S₁, S₂, ..., Sₙ. Gesucht ist eine Auswahl dieser Teilmengen, die jedes Element von U genau einmal enthält — die gewählten Mengen müssen sich also disjunkt überlappen und gemeinsam ganz U abdecken. Das Problem ist NP-vollständig (Karp 1972).
Exact Cover vs. Set Cover
Die Abgrenzung zum verwandten Set Cover ist zentral: Set Cover minimiert die Anzahl gewählter Teilmengen und erlaubt überlappende Abdeckung, Exact Cover verlangt eine Partition — jedes Element liegt in genau einer gewählten Menge. Während Set Cover eine Optimierungsfrage stellt, ist Exact Cover eine reine Existenzfrage. Auch das Vertex Cover ist ein Spezialfall von Set Cover, nicht von Exact Cover.
Algorithmus X und Dancing Links
Der klassische Lösungsweg ist Algorithmus X von Donald Knuth: ein Backtracking-Verfahren, das zeilenweise Teilmengen wählt und alle dadurch erledigten Spalten entfernt. Seine berühmte Implementierung heißt Dancing Links (DLX): Die Matrix wird als Netz doppelt verketteter Listen dargestellt, sodass das Entfernen und Wiederherstellen von Zeilen und Spalten in konstanter Zeit passiert — das Rückgängigmachen im Backtracking wird dadurch extrem schnell.
Wo Exact Cover auftaucht
- Sudoku: Jede Zelle, jede Zeile, jede Spalte und jeder Block erhält eigene Spalten; die Kandidaten werden zu Zeilen — eine exakte Überdeckung entspricht einer gültigen Lösung.
- Pentomino-Puzzles und Polyomino-Legespiele: Teile müssen eine Fläche lückenlos und überlappungsfrei füllen.
- Damenproblem: Positionen von Damen so wählen, dass Felder exakt überdeckt werden.
- Blockpläne und Versuchsdesigns, Ressourcenzuordnung und Dienstplanung mit harten Ausschlussbedingungen.
Modellierung als ganzzahliges Programm
Exact Cover lässt sich direkt als ganzzahliges Programm formulieren: Eine binäre Variable je Teilmenge, und für jedes Element die Nebenbedingung, dass die Summe der gewählten, es enthaltenden Teilmengen genau 1 beträgt. Wo dynamische Programmierung an der Problemgröße scheitert, bleiben Branch and Bound oder Dancing Links die Werkzeuge der Wahl.
Verwandte Grundlagen: Set Cover, Vertex Cover, Backtracking, Satisfiability, Ganzzahlige Optimierung.