X3C to Vertex Cover

X3C

Given: A set of elements X = {x1.. x3n} and a set S of sets {S1..Sm}, such that each set Si, is such that 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 once in S’, and |S’| = n.

Vertex Cover

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

To find: Does G have a vertex cover of size k.

Reduction

Idea:

First reduce X3C to Dominating Set.

Then reduce DS to VC.

Transformation

In terms of transformation, first construct a graph G1, such that G1 DS problem is equivalent to given X3C problem .  Then, transform G1 to G2, such that G1 DS problem is equivalent to G2 VC problem.

Leave a Reply