A linear-time algorithm for semitotal domination in strongly chordal graphs

DOI10.1016/J.DAM.2023.05.030MaRDI QIDQ6110593zbMATH OpenOpenAlexFDO

Authors Vikash Tripathi, Arti Pandey, Anil Maheshwari

Publication date 2 August 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

polynomial-time algorithmsemitotal dominationstrongly chordal graphstotal domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Abstract: In a graph $G=(V,E)$ with no isolated vertex, a dominating set $DsubseteqV$, is called a semitotal dominating set if for every vertex $uinD$ there is another vertex $vinD$, such that distance between $u$ and $v$ is at most two in $G$. Given a graph $G=(V,E)$ without isolated vertices, the Minimum Semitotal Domination problem is to find a minimum cardinality semitotal dominating set of $G$. The semitotal domination number, denoted by $gamm{a}_{t2}(G)$, is the minimum cardinality of a semitotal dominating set of $G$. The decision version of the problem remains NP-complete even when restricted to chordal graphs, chordal bipartite graphs, and planar graphs. Galby et al. in [6] proved that the problem can be solved in polynomial time for bounded MIM-width graphs which includes many well known graph classes, but left the complexity of the problem in strongly chordal graphs unresolved. Henning and Pandey in [20] also asked to resolve the complexity status of the problem in strongly chordal graphs. In this paper, we resolve the complexity of the problem in strongly chordal graphs by designing a linear-time algorithm for the problem.

Review text

A set \(D\) of vertices in an isolate-free graph \(G\) is a semitotal dominating set of \(G\) if \(D\) is a dominating set of \(G\) and every vertex in \(D\) is within distance two from another vertex of \(D\). The semitotal domination number of \(G\) is the minimum cardinality of a semitotal dominating set of \(G\) and is denoted by \(\gamma_{t2}(G)\). The Minimum Semitotal Domination problem is to find a minimum cardinality semitotal dominating set of \(G\). It is known that the decision version of the problem remains NP-complete even when restricted to chordal graphs, chordal bipartite graphs, and planar graphs. The authors in this paper, resolve the complexity of the problem in strongly chordal graphs by designing a linear-time algorithm for the problem.

Recommendations

• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• The semitotal domination problem in block graphs
• An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph
• Algorithmic aspects of semitotal domination in graphs
• Semitotal domination in graphs: partition and algorithmic results

Cites work

• \(k\)-tuple domination in graphs
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• A survey of selected recent results on total domination in graphs
• Algorithmic aspects of semitotal domination in graphs
• An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph
• Characterizations of totally balanced matrices
• Complexity and approximation ratio of semitotal domination in graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Doubly lexical ordering of dense 0--1 matrices
• Doubly Lexical Orderings of Matrices
• Edge weighting functions on semitotal dominating sets
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Labeling algorithms for domination problems in sun-free chordal graphs
• On matching and semitotal domination in graphs
• Perfect graphs involving semitotal and semipaired domination
• Semitotal domination in claw-free cubic graphs
• Semitotal domination in claw-free cubic graphs
• Semitotal domination in graphs
• Semitotal domination in graphs: partition and algorithmic results
• Semitotal domination on AT-free graphs and circle graphs
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Steiner trees, connected domination and strongly chordal graphs
• Structures of domination in graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Three Partition Refinement Algorithms
• Topics in Domination in Graphs
• Total domination in graphs
• Totally-Balanced and Greedy Matrices
• Vertices contained in all or in no minimum semitotal dominating set of a tree

Cited in

(10)

• A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
• The parallel solution of domination problems on chordal and strongly chordal graphs
• Algorithmic aspects of semitotal domination in graphs
• An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph
• The semitotal domination problem in block graphs
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Complexity and approximation ratio of semitotal domination in graphs
• Semipaired Domination in Some Subclasses of Chordal Graphs
• Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
• Approximation algorithm for the semitotal domination problem in unit disk graphs

This page was built for publication: A linear-time algorithm for semitotal domination in strongly chordal graphs

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