Linear kernels for k-tuple and liar's domination in bounded genus graphs

A set $D\subseteq V$ is called a $k$-tuple dominating set of a graph $G=(V,E)$ if $\mid N_G[v]\cap D\mid \ge k$ for all $v\in V$, where $N_G[v]$ denotes the closed neighborhood of $v$. A set $D\subseteq V$ is called a liar’s dominating set of a graph $G=(V,E)$ if (i) $\left| N_G[v] \cap D \right| \geq 2$forall$v\in V$and(ii)foreverypairofdistinctvertices$u, v\in V$,$\left| (N_G[u] \cup N_G[v]) \cap D \right| \geq 3$\mathrm{.}Givenagraph$G$,thedecisionversionsof$k$-Tuple Domination Problem and the Liar’s Domination Problem are to check whether there exists a $k$-tuple dominating set and a liar’s dominating set of $G$ of a given cardinality, respectively. These two problems are known to be NP-complete \cite{LiaoChang2003, Slater2009}. In this paper, we study the parameterized complexity of these problems. We show that the $k$-Tuple Domination Problem and the Liar’s Domination Problem are $\mathsf{W}[2]$-hard for general graphs but they admit linear kernels for graphs with bounded genus.