Exact overlap problem

The exact cover (English Exact Cover ) is a decision problem of combinatorics . It is one of the 21 classic NP-complete problems that Richard M. Karp showed in 1972 to be NP-complete .

Given are a set and a set of non-empty subsets of , that is , where denotes the power set of . ${\displaystyle X}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle S\subseteq {\mathcal {P}}(X)}$ ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle X}$

Find a subset of whose disjoint union is: ${\displaystyle U}$ ${\displaystyle S}$ ${\displaystyle X}$

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

That means: Each element in should occur in exactly one of the sets in . The sets in thus form an exact cover of ( is a partition of ). ${\displaystyle X}$ ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle X}$ ${\displaystyle U}$ ${\displaystyle X}$

Graphic representation of the example (the exact overlap is shown in red)

For example be

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

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

The amount

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

shows that an exact coverage exists.

See also

• Set decomposition problem