Given an undirected graph G = (V,E), does there exist a set D ⊆ V of size k such that every v ∈ V is either in D or adjacent to at least one member of D.

Show that DS∈NPC. You may only assume that VC is known to be NP-Complete.

To prove that DS (Dominating Set) is NP-complete, we need to show two things:

1. DS is in NP: This means that given a solution and an instance of the problem, we can verify the solution in polynomial time.

2. We can reduce the Vertex Cover (VC) problem, which is known to be NP-complete, to DS. This means that if we can solve DS, we can also solve VC.

Let's start with proving that DS is in NP:

For a given set D of vertices, we can check in polynomial time whether every vertex in G is either in D or adjacent to at least one member of D. We can iterate over each vertex and check if it is in D or has an adjacent vertex in D. This can be done in O(|V| + |E|) time, which is polynomial in the size of the input.

Now, let's reduce the VC problem to DS:

Given an instance (G, k) of the VC problem, where G is an undirected graph and k is the size of the vertex cover, we need to construct an instance (G', k') of the DS problem such that (G, k) has a vertex cover if and only if (G', k') has a dominating set.

To do this reduction, we create a new graph G' as follows:
- Add two new vertices u and v to G.
- For each vertex x in G, add an edge between x and u.
- For each edge (x, y) in G, add an edge between x and y in G'.

Now, the reduction is complete. To see why this reduction works:

Suppose (G, k) has a vertex cover V' of size k. Then, the set D = V' ∪ {u} is a dominating set for G' of size k+1. Every vertex in G' is either in D (if it is in V') or adjacent to u (if it is not in V', it must be adjacent to some vertex in V', and u is adjacent to all vertices in G). Therefore, every vertex in G' is either in D or adjacent to at least one member of D.

Conversely, suppose (G', k') has a dominating set D' of size k'. If D' contains u, we can remove u from D' and obtain a dominating set D'' of size k'-1. Since all edges in G' from u only go to vertices in G, removing u does not affect the domination of G'. Therefore, D'' is a dominating set of size k'-1 for G'.

If D' does not contain u, then D' must be a dominating set for G. We can remove v from G' since it does not contribute to the domination of any vertex in G. Therefore, D' is a vertex cover of size k' for G.

Hence, we have shown that (G, k) has a vertex cover if and only if (G', k') has a dominating set.

Since VC is known to be NP-complete, and we have shown the reduction from VC to DS, it follows that DS is also NP-complete.