Algorithm and hardness results on neighborhood total domination in graphs

DOI10.1016/J.TCS.2020.05.002MaRDI QIDQ2201995zbMATH OpenOpenAlexFDO

Authors Anupriya Jha, Dina Pradhan, Sumanta Banerjee

Publication date 17 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.06423

zbMATH Keywords

NP-completenessdominationpolynomial-time algorithmtotal dominationneighborhood total dominationAPX-completeness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: A set $DsubseteqV$ 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$, extsc{Min-NTDS} is the problem of finding a neighborhood total dominating set of $G$ of minimum cardinality. The decision version of extsc{Min-NTDS} is known to be extsf{NP}-complete for bipartite graphs and chordal graphs. In this paper, we extend this extsf{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)$, extsc{Min-NTDS} cannot be approximated within a factor of $(1-varepsilon)log|V|$, unless extsf{NP$subseteq$DTIME($|V{|}^{O(loglog|V|)}$)} and can be approximated within a factor of $O(logDelta)$, where $Delta$ is the maximum degree of the graph $G$. Finally, we show that extsc{Min-NTDS} is extsf{APX}-complete for graphs of degree at most $3$.

Recommendations

• Algorithm complexity of neighborhood total domination and \((\rho,\gamma_{\mathrm{nt}})\)-graphs
• Algorithmic results on locating-total domination in graphs
• Algorithmic aspects of semitotal domination in graphs
• Differentiating-total domination: approximation and hardness results
• Hardness results of global total \(k\)-domination problem in graphs

Cites work

• scientific article; zbMATH DE number 4152428 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A linear time recognition algorithm for proper interval graphs
• A note on domination and total domination in prisms
• A survey of selected recent results on total domination in graphs
• A threshold of ln n for approximating set cover
• Algorithm complexity of neighborhood total domination and \((\rho,\gamma_{\mathrm{nt}})\)-graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Bounds on neighborhood total domination in graphs
• Dominating Sets in Chordal Graphs
• Integer linear programming models for the weighted total domination problem
• Neighborhood total domination of a graph and its complement
• Neighbourhood total domination in graphs
• New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
• On the total \(k\)-domination in graphs
• Optimization, approximation, and complexity classes
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Total $k$-domination in strong product graphs
• Total domination in graphs
• Total forcing versus total domination in cubic graphs
• Trees with large neighborhood total domination number

Cited in

(5)

• Neighbourhood total domination in graphs
• Bounds on neighborhood total domination number in graphs
• Differentiating-total domination: approximation and hardness results
• Nearest neighbour graph realizability is NP-hard
• Algorithm complexity of neighborhood total domination and \((\rho,\gamma_{\mathrm{nt}})\)-graphs

This page was built for publication: Algorithm and hardness results on neighborhood total domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201995)