Dominating Set to Vertex Cover

[I find this transformation to be hard. There are many transformations from other direction (VC to Dominating Set), but not in this direction. This is not finished yet.]

Basic Structure: “Pair”: 2 vertices connected by an edge

Given graph G = (V,E) and integer k, we construct graph G’ = (V’,E’), such that G has a DS of size k iff G’ has a VC of size n + k, where n = |V|.

Each vertex v in V is represented by a pair v1, v2 in V’.   Each pair is connected by an edge.  For every edge {u,v} in E, there exist 4 edges in E’: {u1,v1},{u1,v2},{u2,v1},{u2,v2}.

[Thus given a graph with |V| = n and |E| = m, we construct a graph with |V’| = 2n and |E’| = n + 4m.]

Claim: G has a DS of size k iff G’ has a VC of size n + k, where n = |V|.

Proof:

Firstly, we observe that for any VC in G’, at least one of each “pair” of vertices must be included, since they have an edge between them.

=> If G has a DS of size k, then we can select both vertices from those k pairs, and select any one vertex from each of the other n – k pairs, for a total of n + k nodes in G’.  These n + k nodes must be  a VC.  Why?  Firstly, all edges between the pairs are covered, since we have selected at least one node from each pair.  Consider any other edge in E’.  By construction of G’, this edge must correspond to an edge in E.  Say it corresponds to edge {u,v} in E.

Leave a Reply