# Reduction from dominating set to disconnected dominating set

Consider an undirected graph $$G = \langle V, E\rangle$$, and a set $$S\subseteq V$$ of vertices. We say that $$S$$ is a dominating set, if for every vertex $$v\in V$$, it holds that $$v\in S$$, or $$v$$ has a neighbor in $$S$$. We say that $$S\subseteq V$$ is a disconnected dominating set if it is a dominating set and the subgraph of $$G$$ induces by $$S$$ is not strongly connected (that is, has at least two strongly connected components).

In the dominating set problem, we are given an undirected graph $$G$$ and an integer $$k$$, and we need to decide whether $$G$$ has a dominating set of size at most $$k$$.

In the disconnected dominating set problem, we are given an undirected graph $$G$$ and an integer $$k$$, and we need to decide whether $$G$$ has a disconnected dominating set of size at most $$k$$.

Can we show that the disconnected dominated set problem is NP-hard by a suggesting a PTIME reduction from the dominating set problem?

I was suggested and thought about duplicating the input graph $$G$$.

• What do you mean by "the dominating set has more than one connected component"? Do you mean the subgraph induced by the dominating set is not strongly connected? What have you tried? Commented Jan 11 at 23:36
• the graph is undirected. I meant to say that the subgraph induced by the dominating set is not connected, correct Commented Jan 12 at 0:11
• What is your question? I don't see a question in the body of your post. Please don't force us to infer what your question is.
– D.W.
Commented Jan 12 at 1:16
• I'm sorry, I'm new. I thought the question was clear from the title Commented Jan 12 at 3:12

Consider an undirected graph $$G = \langle V, E\rangle$$, and consider a dominating set $$S\subseteq V$$ in $$G$$. If you mean by "$$S$$ is disconnected" that the subgraph induced by $$S$$ is not strongly connected, then the following is a trivial reduction from dominating set:
On input $$\langle G, k\rangle$$, the reduction outputs $$\langle G', k+1\rangle$$, where $$G'$$ is obtained from $$G$$ by adding a new isolated vertex (a vertex that does not touch any edge).