Algorithm and hardness results on neighborhood total domination in graphs

DOI10.1016/J.TCS.2020.05.002zbMATH Open1458.05197arXiv1910.06423OpenAlexW3024489853MaRDI QIDQ2201995FDOQ2201995

Anupriya Jha, Dina Pradhan, Sumanta Banerjee

Publication date: 17 September 2020

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

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$.

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)

Cites Work

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

Cited In (1)

• Nearest neighbour graph realizability is NP-hard

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)