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 must exactly match .

Reductions

Reduction to SAT

Let be the universe with elements. Let a set of subsets of , i.e. . The goal is to find a , such that:

Let be true if is selected for solution , i.e.:

From that, two conditions of this problem emerge:

1. Every must be contained by at least one , i.e.:

   where , meaning the set of the indices of the set that contain .

2. Every must be contained by at most one .

   where (De Morgan). The condition can be rewritten using index-pairs:

As a result, the SAT CNF formula is: