Algorithm and hardness results on neighborhood total domination in graphs

Abstract A set D ⊆ 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, Min-NTDS is the problem of finding a neighborhood total dominating set of G of minimum cardinality. The decision version of Min-NTDS is known to be NP -complete for bipartite graphs and chordal graphs. In this paper, we extend this 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 ) , Min-NTDS cannot be approximated within a factor of ( 1 − e ) log ⁡ | V | , unless NP ⊆ DTIME ( | V | O ( log ⁡ log ⁡ | V | ) ) and can be approximated within a factor of O ( log ⁡ Δ ) , where Δ is the maximum degree of the graph G. Finally, we show that Min-NTDS is APX -complete for graphs of degree at most 3.