On the complexity of co-secure dominating set problem

DOI10.1016/J.IPL.2023.106463MaRDI QIDQ6195337zbMATH OpenFDO

Authors B. S. Panda, Soumyashree Rana, Sounaka Mishra

Publication date 13 March 2024

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsAPX-completeco-secure dominationdominationinapproximability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: A set $DsubseteqV$ of a graph $G=(V,E)$ is a dominating set of $G$ if every vertex $vinVsetminusD$ is adjacent to at least one vertex in $D.$ A set $SsubseteqV$ is a co-secure dominating set (CSDS) of a graph $G$ if $S$ is a dominating set of $G$ and for each vertex $uinS$ there exists a vertex $vinVsetminusS$ such that $uvinE$ and $(Ssetminusu)cupv$ is a dominating set of $G$. The minimum cardinality of a co-secure dominating set of $G$ is the co-secure domination number and it is denoted by $gamm{a}_{cs}(G)$. Given a graph $G=(V,E)$, the minimum co-secure dominating set problem (Min Co-secure Dom) is to find a co-secure dominating set of minimum cardinality. In this paper, we strengthen the inapproximability result of Min Co-secure Dom for general graphs by showing that this problem can not be approximated within a factor of $(1-epsilon)ln|V|$ for perfect elimination bipartite graphs and star convex bipartite graphs unless P=NP. On the positive side, we show that Min Co-secure Dom can be approximated within a factor of $O(ln|V|)$ for any graph $G$ with $delta(G)geq2$. For $3$-regular and $4$-regular graphs, we show that Min Co-secure Dom is approximable within a factor of $dfrac83$ and $dfrac103$, respectively. Furthermore, we prove that Min Co-secure Dom is APX-complete for $3$-regular graphs.

Cites work

• Algorithmic complexity of secure connected domination in graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Co-secure and secure domination in graphs
• Co-secure domination in Mycielski graphs
• Complexity results on cosecure domination in graphs
• scientific article; zbMATH DE number 1954391 (Why is no real title available?)
• scientific article; zbMATH DE number 2188604 (Why is no real title available?)
• On computing secure domination of trees
• On secure domination in graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Secure domination and secure total domination in graphs
• Secure domination in cographs
• The co-secure domination in proper interval graphs
• The complexity of secure domination problem in graphs
• Topics in Domination in Graphs

Cited in

(3)

• The algorithm and complexity of co-secure domination in geometric intersection graphs
• On the parameterized complexity of cosecure domination
• Corrigendum to: ``On the complexity of co-secure dominating set problem

This page was built for publication: On the complexity of co-secure dominating set problem

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