Cosecure domination: hardness results and algorithms

DOI10.1007/978-3-031-34347-6_21MaRDI QIDQ6182909zbMATH OpenOpenAlexFDO

Authors Kusum, Arti Pandey

Publication date 22 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessbipartite graphsdoubly chordal graphsbounded tree-width graphscosecure domination

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Abstract: For a simple graph $G=(V,E)$ without any isolated vertex, a cosecure dominating set $D$ of $G$ satisfies the following two properties (i) $S$ is a dominating set of $G$, (ii) for every vertex $vinS$ there exists a vertex $uinVsetminusS$ such that $uvinE$ and $(Ssetminusv)cupu$ is a dominating set of $G$. The minimum cardinality of a cosecure dominating set of $G$ is called cosecure domination number of $G$ and is denoted by $gamm{a}_{cs}(G)$. The Minimum Cosecure Domination problem is to find a cosecure dominating set of a graph $G$ of cardinality $gamm{a}_{cs}(G)$. The decision version of the problem is known to be NP-complete for bipartite, planar, and split graphs. Also, it is known that the Minimum Cosecure Domination problem is efficiently solvable for proper interval graphs and cographs. In this paper, we work on various important graph classes in an effort to reduce the complexity gap of the Minimum Cosecure Domination problem. We show that the decision version of the problem remains NP-complete for circle graphs, doubly chordal graphs, chordal bipartite graphs, star-convex bipartite graphs and comb-convex bipartite graphs. On the positive side, we give an efficient algorithm to compute the cosecure domination number of chain graphs, which is an important subclass of bipartite graphs. In addition, we show that the problem is linear-time solvable for bounded tree-width graphs. Further, we prove that the computational complexity of this problem varies from the domination problem.

Cites work

• scientific article; zbMATH DE number 2188604 (Why is no real title available?)
• Co-secure and secure domination in graphs
• Co-secure domination in Mycielski graphs
• Complexity results on cosecure domination in graphs
• Correcting the algorithm for the secure domination number of cographs by Jha, Pradhan, and Banerjee
• Dominating sets for split and bipartite graphs
• Doubly chordal graphs, steiner trees, and connected domination
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On secure domination in graphs
• Reducibility among combinatorial problems
• Secure domination and secure total domination in graphs
• Secure domination in cographs
• Structures of domination in graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• The co-secure domination in proper interval graphs
• The complexity of secure domination problem in graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Topics in Domination in Graphs
• Two Hardness Results on Feedback Vertex Sets

This page was built for publication: Cosecure domination: hardness results and algorithms

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