Question

Question: In an undirected graph $\mathit{G}\mathbf{=}\mathbf{(}\mathit{V}\mathbf{,}\mathit{E}\mathbf{)}$, we say $\mathit{D}\mathbf{\subseteq }\mathit{V}$is a dominating set if every $\mathit{v}\mathbf{\in }\mathit{V}$ is either in D or adjacent to at least one member of D. In the DOMINATING SET problem, the input is a graph and a budget , and the aim is to find a dominating set in the graph of size at most , if one exists. Prove that this problem is NP-complete.

Short answer

Any vertex cover problem can be reduced to the dominance set problem.

Step-by-step solution

Define vertex cover problem

The vertex Cover problem for an undirected graph$G(V,E)$ , is said to be$S\subseteq V$ vertex cover, if and only if any edge of graph G is adjacent to at least one vertex in S. It is NP-complete problem.

Any vertex cover problem is reduced to the dominating set problem

Prove that the graph  as NP-Complete problem

Consider an undirected graph G, for any side uv of the graph G , add a point t so that the two vertices u and v of the side are in phase with t respectively. Get a new undirected graph G'.

If the original undirected G graph has a vertex cover S , and S satisfies$\left|S\right|\le b$ , then can also be used as a dominating set of graphs G' that satisfies the conditions.

Assume is not the dominating set of the graph G', that is, there is a point $t\in V\left(G^{\text{'}}\right)$so that $t\notin S$and t is not adjacent to any vertex in s . Since the graph g is connected, there must be edges (u,t) satisfying $u\notin S$.

The edge ( u,t ) bis an auxiliary edge added to the original graph.

When the edge corresponding to $t$is $\left(u,v\right)$, is a cover of G, and the vertex u of the $\left(u,v\right)$edge does not belong to$S$, then vertex $v$must belong to $S$.

If is adjacent to$v$ , then it $S$is proved that if is a vertex cover of the undirected graph$G$, and $\left|S\right|\le b$, then$S$ is the dominating set of the graph$G\text{'}$ .

Therefore, any vertex cover problem can be reduced to the dominance set problem.