On the Parameterized Complexity of Semitotal Domination on Graph Classes

Abstract

For a given graph $G=(V,E)$, a subset of the vertices $D\subseteq V$ is called a semitotal dominating set, if $D$ is a dominating set and every vertex $v\in D$ is within distance two to another witness $v^{\prime }\in D$. We want to find a semitotal dominating set of minimum cardinality. We show that the problem is $\mathrm{W}[2]$-hard on bipartite and split graphs when parameterized by the solution size $k$. On the positive side, we extend the kernelization technique of Alber, Fellows, and Niedermeier [JACM 2004] to obtain a linear kernel of size $358k$ on planar graphs. This result complements known linear kernels already known for several variants, including Total, Connected, Red-Blue, Efficient, Edge, and Independent Dominating Set.

Master Thesis in Computer Science