Algorithmic Aspects of Semitotal Domination in Graphs

For a graph $G=(V,E)$, a set $D\subseteq V$ is called a semitotal dominating set of $G$ if $D$ is a dominating set of $G$, and every vertex in $D$ is within distance~$2$ of another vertex of~$D$. The \textsc{Minimum Semitotal Domination} problem is to find a semitotal dominating set of minimum cardinality. Given a graph $G$ and a positive integer $k$, the $\text{textsc}SemitotalDominationDecision$ problem is to decide whether $G$ has a semitotal dominating set of cardinality at most $k$. The \textsc{Semitotal Domination Decision} problem is known to be NP-complete for general graphs. In this paper, we show that the $\text{textsc}SemitotalDominationDecision$ problem remains NP-complete for planar graphs, split graphs and chordal bipartite graphs. We give a polynomial time algorithm to solve the \textsc{Minimum Semitotal Domination} problem in interval graphs. We show that the $\text{textsc}MinimumSemitotalDomination$ problem in a graph with maximum degree~$\mathrm{\Delta }$ admits an approximation algorithm that achieves the approximation ratio of $2+3\ln (\mathrm{\Delta }+1)$, showing that the problem is in the class log-APX. We also show that the $\text{textsc}MinimumSemitotalDomination$ problem cannot be approximated within $(1-ϵ)\ln \mathrm{\mid }V\mathrm{\mid }$ for any $ϵ>0$ unless NP $\subseteq$ DTIME $(\mathrm{\mid }V{\mathrm{\mid }}^{O(\log \log \mathrm{\mid }V\mathrm{\mid })})$. Finally, we prove that the $\text{textsc}MinimumSemitotalDomination$ problem is APX-complete for bipartite graphs with maximum degree $4$.