1
$\begingroup$

The domination problem $DOM$ is defined as $$ DOM = \{ \langle G,k \rangle\ | \ G \text{ has a domination of size } k, K \in \mathbb{N} \}, $$ and the rainbow domination problem $RDOM$ is defined as $$ RDOM = \{ \langle G,r,k \rangle \ | \ G \text{ has a r-dominating set of size } k; r,k \in \mathbb{N} \}. $$ A $r$-rainbow domination for a graph $G=(V,E)$ is a mapping of the form $f:V \rightarrow 2^{\{ 1,\ldots, r\}}$ such that $f(v) = \emptyset$ implies $\cup_{u \in N(v)} f(u) = \{ 1,\ldots , r\}$ where $N(v) = \{ u \ | \ \{u,v\} \in E \}$. The size of $r$-domination is defined as $\sum_{v \in V} |f(v)|$.

To show that $RDOM$ is $\mathbf{NP}$-hard, one must show that $DOM \leq_P RDOM$, i.e. given an instance $\langle G,k \rangle$, construct an instance $\langle G',r,k' \rangle$ in polynomial time such that $\langle G,k \rangle \in DOM$ if and only if $\langle G',r,K' \rangle \in RDOM$.

My friend states that we know that a domination is a $1$-rainbow domination in the same graph, i.e. domination is a special kind of rainbow-domination, and since domination is $\mathbf{NP}$-hard, then $RDOM$ is also $\mathbf{NP}$-hard. How to convince him that this is wrong? or this argument is correct?

$\endgroup$
  • 1
    $\begingroup$ Using special cases is indeed a valid reduction technique -- if you do it in the correct direction. $\endgroup$ – Raphael Jul 4 '16 at 9:06
  • $\begingroup$ @Raphael Thanks for the comment. Therefore, if someone directly shows that $3SAT$ is NP-complete, then $SAT$ would be NP-hard since $3SAT$ is a special case of $SAT$. $\endgroup$ – Ali Shakiba Jul 4 '16 at 17:00
2
$\begingroup$

There are two statements here that rule the argument. The first statement:

Statement 1. To show that $RDOM$ is $\mathbf{NP}$-hard, one must show that $DOM \leq_P RDOM$, i.e. given an instance $\langle G,k \rangle$, construct an instance $\langle G',r,k'\rangle$ in polynomial time such that $\langle G,k \rangle \in DOM$ if and only if $\langle G',r,K'\rangle \in RDOM$.

is a general framework for showing that RDOM is NP-hard. However, in this statement, you have not shown how to prove that this reduction works. You just said how to prove that this problem (or any problem) is NP-hard. In order to prove it, you need a proper reduction from all instances of DOM to instances of RDOM. The second argument however,

Statement 2. By the way, my friend states that we know that a domination is a $1$-rainbow domination in the same graph, i.e. domination is a special kind of rainbow-domination, and since domination is $\mathbf{NP}$-hard, then $RDOM$ is also $\mathbf{NP}$-hard. How to convince him that this is wrong? or Is this argument correct?

looks like a proper reduction. If "every domination is a $1$-rainbow domination in the same graph", then this proof is completely right. This is a proper reduction from every instance of DOM problem to instances of RDOM or 1DOM problem. However, if "every domination is NOT a $1$-rainbow domination in the same graph", then this proof is completely wrong.

My understanding is that a domination, can be any of 1-rainbow domination, ...,or |V|-rainbow domination. In this case, it is implied that by having a polynomial algorithm for RDOM problem, you can iterate $|V|$ times thorough $r$-dominations and determine if the graph is dominating. Thus, if you have a polynomial algorithm for RDOM problem, you can solve the DOM problem polynomially.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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