Before revision:  That is, the set D satisfies the condition that |N[v]\cap D|\geq 1 for each v\in V, where N[v] is the closed neighborhood of v. In this paper, we study two variants of the classical dominating set problem: k-tuple dominating set (k-DS) problem and Liar's dominating set (LDS) problem, and obtain several algorithmic and hardness results.
After revision:  That is, the set D satisfies the condition that |N[v]\cap D|\geq 1 for each v\in V, where N[v] is the closed neighborhood of v. In this paper, we study two variants of the classical dominating set problem: -tuple dominating set (k-DS) problem and Liar's dominating set (LDS) problem, and obtain several algorithmic and hardness results.