  Given a graph $G=(V,E)$, the dominating set problem asks for a minimum subset
of vertices $D\subseteq V$ such that every vertex $u\in V\setminus D$ is
adjacent to at least one vertex $v\in D$. 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: $\boldmath{k}$-tuple dominating set ($k$-DS)
problem and Liar's dominating set (LDS) problem, and obtain several algorithmic
and hardness results.
  On the algorithmic side, we present a constant factor
($\frac{11}{2}$)-approximation algorithm for the Liar's dominating set problem
on unit disk graphs. Then, we obtain a PTAS for the $\boldmath{k}$-tuple
dominating set problem on unit disk graphs. On the hardness side, we show a
$\Omega (n^2)$ bits lower bound for the space complexity of any (randomized)
streaming algorithm for Liar's dominating set problem as well as for the
$\boldmath{k}$-tuple dominating set problem. Furthermore, we prove that the
Liar's dominating set problem on bipartite graphs is W[2]-hard.
