91Ó°ÊÓ

Given a graph \(G = (V, E)\) and an integer \(k\), DOMINATING-SET is the decision problem of whether there is a subset \(D \subseteq V\) with \(|D| \leq k\) such that each node in \(V \setminus D\) is adjacent to at least one node in \(D\). To show that DOMINATING-SET belongs to NP, we need to demonstrate that, given a certificate (a possible solution) \(D\), we can verify in polynomial time that \(D\) is a valid dominating set of \(G\) of size at most \(k\). Given a subset \(D\) of \(V\), we can check whether it is a dominating set by iterating through the nodes in \(V \setminus D\), and for each node, checking if at least one of its neighbors is in \(D\). This process takes polynomial time in the number of vertices and edges in \(G\). Since the size of \(D\) is bounded by \(k\), which is given as input, this verification process is polynomial in the input size. Therefore, DOMINATING-SET belongs to NP.

Now, we need to show that any instance of the VERTEX-COVER problem can be reduced to an instance of the DOMINATING-SET problem in polynomial time. Let's consider an instance of VERTEX-COVER given by a graph \(G = (V, E)\) and an integer \(m\). We will transform this instance of VERTEX-COVER into an instance of DOMINATING-SET as follows: Create a new graph \(G' = (V', E')\), where: 1. For each edge \((u, v) \in E\), create a new vertex \(w_{u,v}\) in \(V'\). 2. For each vertex \(v \in V\), create an edge in \(E'\) between \(v\) and all the new vertices \(w_{u,v}\) such that \((u, v) \in E\). Now, we transform the instance of VERTEX-COVER \((G, m)\) into the instance of DOMINATING-SET \((G', m)\). This transformation can be done in polynomial time with respect to the input size, as we only need to iterate through the vertices and edges in \(G\) and create new vertices and edges in \(G'\) accordingly.

Finally, we need to show that there exists a vertex cover of size \(m\) in \(G\) if and only if there exists a dominating set of size \(m\) in \(G'\). If there exists a vertex cover of size \(m\) in \(G\), then each edge must be incident to at least one vertex in the vertex cover. By construction, these vertices in the vertex cover also form a dominating set of size \(m\) in \(G'\), as every new vertex \(w_{u,v}\) corresponding to an edge \((u, v)\) in \(G\) will be adjacent to either \(u\) or \(v\), as required. Conversely, if there exists a dominating set of size \(m\) in \(G'\), then all vertices in \(V'\) are either in the dominating set or have neighbors in the dominating set. Since the new vertices \(w_{u,v}\) are only connected to the original vertices in \(V\), the dominating set in \(G'\) must contain at least one vertex from each edge \((u, v) \in G\). Therefore, the set of original vertices in the dominating set of \(G'\) forms a vertex cover of size \(m\) in \(G\). Thus, we have shown that the DOMINATING-SET problem is NP-complete by giving a reduction from the VERTEX-COVER problem, completing the proof.