### X3C

Given: A set of elements X = {x1.. x3n} and a set S of sets {S1..Sm}, such that each set Si is a subset of X, and |Si| = 3.

To find if there exists Exact 3 Cover S’ subset of S, such that each element of X is represented in S’, and |S’| = n.

### Dominating Set

Given: A graph G = (V,E) and an integer k.

To find: Does G have a dominating set of size k.

#### Transformation

Given an instance of X3C with 3n elements and m sets, construct a graph G1 with 3n + m + 1 + (n + 2) vertices. G1 is a layered graph, with following layers:

- First layer has 3n vertices corresponding to 3n elements in X3C.
- Second layer has m vertices corresponding to m sets in X3C.
- Third layer has a solitary vertex, y.
- Fourth layer has n + 2 vertices.

Edges:

- y is connected to all vertices of the fourth layer.
- y is connected to all vertices of the second layer.
- Vertices of the first layer are connected to the vertices of the second layer based on the set membership of X3C.

**Claim**: X3C has an exact 3 cover iff G1 has a DS of size n + 1.

**Proof**:

=> Say X3C has an exact 3 cover. Then, select the vertices from the second layer corresponding to the exact 3 cover. These vertices plus y must be a DS in G1.

<= Say G1 has a DS of size n + 1. Then, due to nature of G1, y must in DS. (Otherwise entire 4th layer needs to be in DS, that is more than n + 1 nodes.) Next, suppose p1 nodes of DS come from layer 1, p2 nodes from layer 2. Then p1 + p2 = n. The maximum number of nodes that can be dominated by p1 nodes from layer 1 and p2 nodes from layer 2 = p1 + 3 p2.

So p1 + 3 p2 >= 3n.

That is, n – p2 + 3 p2 >= 3n. That is, p2 >= n. That is, all n nodes of DS (other than y) must be from layer 2. These n nodes must be dominating all of layer 1, so sets corresponding to this must be an exact 3 cover.