Secure connected domination and secure total domination in unit disk graphs and rectangle graphs

• Published in: Theoretical computer science 2023-05, Vol.957, p.113824, Article 113824
• Main Authors: Wang, Cai-Xia, Yang, Yu, Xu, Shou-Jun
• Format: Article
• Language: English
• Subjects: Approximation algorithm; NP-complete; Rectangle graphs; Secure connected domination; Secure total domination; Unit disk graphs
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2023.113824

Given a graph G with vertex set V, a secure connected (resp. total) dominating set of G is a connected (resp. total) dominating set S⊆V with the property that for each u∈V∖S, there exists v∈S adjacent to u such that (S∪{u})∖{v} is a connected (resp. total) dominating set of G. The minimum secure connected dominating set (or, for short, MSCDS) (resp. minimum secure total dominating set (or, for short, MSTDS)) problem is to find an MSCDS (resp. MSTDS) in a given graph. In this paper, we initiate to consider complexity and algorithmic aspects of the MSCDS problem and the MSTDS problem in unit disk graphs and rectangle graphs. Firstly, we show that the decision version of the MSCDS problem is NP-complete in unit square graphs and unit disk graphs. Then we show that the decision version of the MSTDS problem is NP-complete even in grid graphs (a subclass of unit square graphs and unit disk graphs). Secondly, we give linear-time constant-approximation algorithms for the two problems in unit square graphs, unit disk graphs and unit-height rectangle graphs. Thirdly, we propose a PTAS for the MSTDS problem in unit square graphs and unit disk graphs. Finally, we show that the two problems in proper rectangle graphs are APX-hard. Further we give an explicit lower bound 1.00147 on efficient approximability for the two problems in proper rectangle graphs unless P=NP.