Question

7.(35) A subset S of the nodes of a graph G is a dominating set if every other node of G is adjacent to some node in S. Consider the language: DOMINATING-SET ={<G, K> | G has a dominating set with k nodes} Show that DOMINATING-SET is NP-complete by reduction from VERTEX- COVER.

Answer 1

answer

Solution: A problem is said to be NP complete if it is both NP and NP hard. To show that the DOMINATING-SET problem is NP complete, the reduction must be performed from VERTEX-COVER problem. To show: VC <, Dominating-set and DS E NP Proof Vertex cover problem is a NP complete problem. It is required to produce an instance (G,K) of the dominating set problem from the instance (G, k) of the vertex cover problem such that G has the vertex cover having size k if G' has dominating set having size k'. According to vertex cover problem, each edge is incident to vertex in V, so here incidence of edges is to be considered. According to dominating set problem, each vertex is either in V or is adjacent to a vertex in V, so here adjacency of vertices is to be considered. Here, the reduction has to be done from the edges of G to vertices of G'. Create a graph Gº and insert a vertex in middle of each edge of the graph G. Suppose. {u, v} is the edge in graph G, then create a new vertex x, such that the edge {u, v} is replaced by two edges {u, x,y} and {v. X}. Now, from {u. xx} and {v, x,), it can be said that u is incident to the new vertex x Thus, if G has the vertex cover having size s, then G' has dominating set of size s. Proving the problem backwards: Let Gº have dominating set d' having s nodes. Construct a cover of G as follows: Since. x, was the new vertex that was being created, so the set d' must contain either u, v or X,. Thus, the set d' is the vertex cover of size s. Therefore, if G' has the dominating set having size s. then G has the vertex cover of size s. DS E NP : Suppose an instance (G, k) for dominating set is given then guess the certificate consisting of k vertices that form the dominating set. It is required to verify that the given vertices will form a dominating set. Check that if every vertex belongs to the set. then output “yes” or if it is adjacent to the vertex in the set then output “no”. Thus, reduction is complete and DOMINATING SET problem is NP complete