2.A Dominating Set of a graph is a collection of vertices which cover every vertex not in that collection i.e. every vertex not in the collection is connected to at least one vertex in the collection. Formally, given a graph G = (V,E), a dominating set of G is set of the vertices such that every vertex is joined to at least one vertex in V' by an edge in E. So for example, consider the graph in Fig HW4Q2a

On this graph, {1, 2, 3} is a dominating set, since 4 is connected to 2, 5 is connected to 3, and 6 is connected to 2. {1, 6,4, 5} is a dominating set, since 2 is connected to 1, and 3 is connected to 1. {1, 2, 6} is not a dominating set, since 5 is not connected to 1, 2 or 6. The Dominating Set problem can be described as follows: Input: An undirected graph G = (V,E), a number q. YES/NO Question: Does G have a dominating set of size q. So, on the above example, the answer would be YES with q = 2 (since {2,3} is a dominating set), YES with q = 3, YES with q = 4, but NO with q = 1. Now we describe the Set Cover problem. Suppose we have a set X, and a collection F of subsets of X. A set cover is a collection of some of the subsets from F which "covers" X i.e. whose union is X. For example, suppose X = {1, 2, 3, 4, 5}, F = {{1, 2, 4}, {2, 3}, {4}, {2} ,{5} ,{2 ,4}}. The collection F' = {{1, 2, 4}, {2, 3},{5}} covers X since {1, 2 , 4} {2 , 3} {5} = {1, 2, 3 , 4 , 5,}= X. However, the collection F''= {{2, 3}, {4} ,{2}, {2 , 4}} does not cover X since {2, 3} {4} {2} {2,4} = {2, 3, 4} X. The set cover problem asks the question whether, for a given number k, does there exist a set cover of size k. For example, on the above sets, for k = 3 the answer would be YES (we saw a set cover with 3 sets), for k = 4 the answer would be YES, but for k = 2, the answer would be NO (because no two subsets from F cover X). Formally, the Set Cover problem can be described as follows: Input: A set X and a collection F of subsets of X, and a number k. YES/NO Question: Is there a collection of k subsets from F whose union is X? Your job: nd a polynomial-time reduction from the Dominating Set problem to the Set Cover Problem. Hint: i)Pick X to be equal to the set V . ii)You now have to gure out what F and k should be. Remember that what you want is that if there is a dominating set of size q, there should be collection of k subsets from F that should cover X. So, in a sense, what you want to do is to have a subset of F represent a vertex of V in some way (you have to ll in the details here) and a small dominating set correspond to a small set cover in some way. iii)As an additional hint, the number of subsets of F will equal the number of vertices in the graph G. (a) Give a short and clear description of your reduction as follows. i)The input to your reduction will be an arbitrary instance of the Dominating Set problem i.e. a graph G = (V,E), and a number q. ii)You have to say what the output of your reduction will be i.e. you have to describe the instance of the Set Cover problem produced by your reduction. You will do this by specifying: i. what will be the set X, ii. will be the collection F,a iii. what will be the number k. (b) Show how your reduction will translate the YES instance (q = 3) and the graph in Fig HW4Q2b of the Dominating Set Problem into a YES instance for Set Cover by describing X,F, k for this G, q and arguing why it is a YES instance

for Set Cover.

.

(c) Show how your reduction will translate the NO instance (q = 2) and the graph in Fig HW4Q2c of the Dominating Set Problem into a NO instance for Set Cover by describing X; F; k for this G; q and arguing why it is a NO instance for Set Cover.

Question is from Algorithm analysis and design