X3C to Dominating Set

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.

Back to reductions

Leave a Reply