Algorithm and hardness results on neighborhood total domination in graphs

A set $D\subseteq V$ of a graph $G=(V,E)$ is called a neighborhood total dominating set of $G$ if $D$ is a dominating set and the subgraph of $G$ induced by the open neighborhood of $D$ has no isolated vertex. Given a graph $G$, $\text{textsc}Min-NTDS$ is the problem of finding a neighborhood total dominating set of $G$ of minimum cardinality. The decision version of $\text{textsc}Min-NTDS$ is known to be $\mathsf{\text{NP}}$-complete for bipartite graphs and chordal graphs. In this paper, we extend this $\mathsf{\text{NP}}$-completeness result to undirected path graphs, chordal bipartite graphs, and planar graphs. We also present a linear time algorithm for computing a minimum neighborhood total dominating set in proper interval graphs. We show that for a given graph $G=(V,E)$, $\text{textsc}Min-NTDS$ cannot be approximated within a factor of $(1-\epsilon )\log \mathrm{\mid }V\mathrm{\mid }$, unless \textsf{NP$\subseteq$DTIME($|V|^{O(\log \log |V|)})} and can be approximated within a factor ofO(\log \Delta)$,where$\Delta$isthemaximumdegreeofthegraph$G$. Finally, we show that $\text{textsc}Min-NTDS$ is $\mathsf{\text{APX}}$-complete for graphs of degree at most $3$.