# Is this argument wrong “since DOM is special kind of RDOM, then RDOM is NP-hard”?

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?

• Using special cases is indeed a valid reduction technique -- if you do it in the correct direction. – Raphael Jul 4 '16 at 9:06
• @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$. – Ali Shakiba Jul 4 '16 at 17:00

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