1
$\begingroup$

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$.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Bader Abu Radi
    Commented Jan 11 at 23:36
  • $\begingroup$ the graph is undirected. I meant to say that the subgraph induced by the dominating set is not connected, correct $\endgroup$
    – Zumikya
    Commented Jan 12 at 0:11
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Jan 12 at 1:16
  • $\begingroup$ I'm sorry, I'm new. I thought the question was clear from the title $\endgroup$
    – Zumikya
    Commented Jan 12 at 3:12

1 Answer 1

Reset to default
3
$\begingroup$

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).

Correctness follows from the fact that a dominating set must contain all isolated vertices, and I leave the details to you.

Improve this answer
$\endgroup$
4
  • $\begingroup$ thank you for your answer! I was suggested to duplicate G for the transformation. I thought that the disconnected dominating set would be (the original dominating set) U (the copy of the dominating set). And it would be disconnected because there would not be edges between G and its copy. I'm not sure if it is wrong or if I explained it badly but my professor didn't consider it 100% right. What would you do if you had to duplicate G? $\endgroup$
    – Zumikya
    Commented Jan 12 at 0:09
  • $\begingroup$ Your solution is fine, but there is really no need to duplicate the whole graph. A single additional isolated vertex suffices. You should ask your professor what he/she didn't like about your solution. $\endgroup$
    – Bader Abu Radi
    Commented Jan 12 at 0:13
  • $\begingroup$ thank you so much $\endgroup$
    – Zumikya
    Commented Jan 12 at 0:17
  • $\begingroup$ If you think the answer is useful you can choose it as a correct answer. Also, it would be good if you edit your question to make it clearer after our discussion in the comments. Meaning, explicitly write in the question what you mean by disconnected dominating set to help other people that read the question get the point. $\endgroup$
    – Bader Abu Radi
    Commented Jan 12 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.