Ho! Ho! Ho! Merry Christmas!\" Christmas is all around and Santa Claus is prepar

Question

Ho! Ho! Ho! Merry Christmas!" Christmas is all around and Santa Claus is preparing his list to send out gifts to nice children. However, in your childhood, have you wondered how Santa Claus knows that you are a naughty child or a nice child? The secret is that Santa's Elves are assigned to evaluate every child in towns during the year. To carry out such hard work, Santa Claus quietly sets up Santa Claus Intelligence Agency, also known as SCIA, in towns to manage his Elves. From Santa Claus's point of view, the world can be viewed as a connected graph. Each town is a vertex in the graph and for every pair of adjacent towns there is an edge between them. To avoid being noticed, Santa Claus sets up as few SCIAs as possible. His rules are as follows. First, there is at most one SCLA in a town. Second, a town that doesn't have a SCIA must be adjacent to at least one town with a SCIA To thank you for your hard work in this semester and celebrate the holiday, I will kindly tell you that Santa Claus is facing the dominating-set problem In graph theory, a dominating set for a graph G = (V, E) is a subset V' of V such that every vertex not in V' is adjacent to at least one member of V'. The dominating-set problem is to find a minimum dominating set in G. In this problem, we only take connected graphs into consideration. (2%) The related decision problem for the dominating-set problem can be defined as DMT(G, k) {Does graph G has a dominating set of size k} Suppose you are given a subroutine DMT(G, k) to solve the decision problem. Please formulate a polynomial-time algorithm to find the minimum size of dominating set for a connected graph G using this subroutine. You can assume the running time of calling this subroutine is O(1) (8%) Given a connected graph H, please give a reduction algorithm to find a vertex cover of size k in H (V_h, E_h) using the subroutine DMT(G, k) in part(1). The running time of your reduction algorithm should be polynomial in |V_h| and |E_h| (7%) With part(1) and part (2), prove that the dominating-set problem is NP-complete. (3%) However, the same problem might be solvable in polynomial time on certain types of graphs such as tree, block graph, etc. Please give a polynomial-time algorithm to solve the dominating set problem in a tree

Explanation / Answer

Given Rules:
1. There is at most one SCIA in a town .
2.Each town is vertex in the graph.
3.if a town does not have any SCIA then it should be adjacent to atleast one town with SCIA in the graph.

Assumption

Let G=(V,E) is a graph containing town as vertices and e as edges to the vertices.

where v'of such that every vertex is not in V, is adjacent to at leat one member of v'.

1)DMT(G,K) is the dominating set having the minimum size k. the following the are the steps to find minimusize of given DMT

    a.find a vertex from the graph which is having maximum number neighbours.
   b.add that vertex to the dominating set.
   c.remove the seleted vertex and its neighbours from the graph.
   d.repeat the step b & c untill graph contains no vertices.
  

2 ) let H=(Vh,Eh) is vertexcover where vh belongs to Vertex in Graph g and Eh belongs to Edge in the Graph G.
The following are the steps to find a vertex cover of size k
  
  
   a) Add a vertex from the Dominating Set (G,k) into the Vertex Cover H(Vh,Eh).
  
   b) vertex cover only contians vertices having the maximum number of incident edges,so it is clearly show that size of the vertex cover will not

exceed the size of DMT.
   c)Garph G contains Vertex cover smaller than k,Since it is computed Using DMT which is having size k.

3) from the above 1 & 2
   Vertex Cover is nothing but DMT ,we know that dominating set problem is NP Now we have to show that Vertex Cover is NP Complete,

   Vertex Cover is H = (V, E) and size of the vertex cover is smaller than k.

Let’s prove dominating set is NP Complete.
Let V=0,k=0,then the vertices in V will covers all the edges in E.so the Dominating set also satifies for v=0
for v={v1,v2..Vk} k={1,2,....K}

Since any subset Vi is the set of edges incident on vertex i,is the union of all vi such that i V contains all the edges in E. so here also it covers all

edges in E inpolynomial times.so Dominating Set also satisifies for all k.
Finally we can say that Dominating Set is NP-Complete,since the reduction can be done in polynomial time.

4)Solving DMT in a tree
   a)take a leaf and get its parent.
   b)put the parent in Dominating set and remove its leaves.
   c)Now get the parent for the parent ,if the parent is not in the dominating set then add it and remove its leafs.
   d) check whether the leafs of parent that is not dominated exists,then add them to Dominating Set.
   e)repeat until we get DMT(G,k) with minimum size k

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.