Exact Cover Problem

computation

Definition

Exact Cover Problem

The Exact Cover Problem is a variant of the Set Cover Problem. The union of all subsets $S_i\in C$ must exactly match $U$.

Reductions

Reduction to SAT

Let $U=\{u_1,u_2,\dots ,u_n\}$ be the universe with $n$ elements. Let $C=\{S_{1}1,S_2,\dots ,S_m\}$ a set of subsets of $U$, i.e. $S_j\subseteq U$. The goal is to find a $C\subseteq S$, such that:

$$\forall u\in U:\exists !S_j\in C:u\in S_j$$

Let $x_j$ be true if $S_j$ is selected for solution $C$, i.e.:

$$x_j⟺S_j\in C$$

From that, two conditions of this problem emerge:

1. Every $u\in U$ must be contained by at least one $S_j$, i.e.:

   $$\forall u\in U:\exists j\in \text{indices}(u):x_j$$

   where $\text{indices}(u)=\{j\mid u\in S_j\}$, meaning the set of the indices of the set that contain $u\in U$.

2. Every $u\in U$ must be contained by at most one $S_j$.

   $$\forall u\in U:\forall S_a\ne S_b:u\in S_a\wedge u\in S_b⟹\neg (x_a\wedge x_b)$$

   where $\neg (x_a\wedge x_b)=\neg x_a\vee \neg x_b$ (De Morgan). The condition can be rewritten using index-pairs:

   $$\forall u\in U:\forall a<b:(u\in S_a\wedge b\in S_b)⟹(\neg x_a\vee \neg x_b)$$

As a result, the SAT CNF formula is:

$$\Phi (x_1,x_2,\dots ,x_m)=\left(\underset{u\in U}{\bigwedge }\underset{j\in \text{indices}(u)}{\bigvee }{x}_j\right)\wedge \left(\underset{u\in U}{\bigwedge }\underset{\begin{array}{c}a<b\\ u\in S_a\\ u\in S_b\end{array}}{\bigwedge }(\neg x_a\vee \neg x_b)\right)$$