Problem der exakten Überdeckung

Problemstellung:

Gegeben: Familie $F = \{S_1 ,\ldots, S_n \}$ von $n$ Teilmengen einer Menge $U = \{u_1 ,\ldots, u_{3m}\}$ mit $|S_j | = 3$ für alle $j = 1, \ldots , n$. Entscheide: Gibt es eine Teilfamilie von $F$ mit $m$ Teilmengen $S_{i_1},\ldots,S_{i_m}$ und $\bigcup_{j=1,\ldots,m}S_{i_j}=S$?

Satz: Problem der exakten Überdeckung

Problem der exakten Überdeckung ist NP-vollständig.

Beweis Idee: Jede Instanz von 3-dimensional matching kann auch als Instanz von 3-Exact Cover aufgefasst werden.

#TODO Visualisieren