Algorithmic and complexity aspects of problems related to total restrained domination for graphs

• Published in: Journal of combinatorial optimization 2023-12, Vol.46 (5), Article 28
• Main Authors: Yang, Yu, Wang, Cai-Xia, Xu, Shou-Jun
• Format: Article
• Language: English
• Subjects: Algorithms; Apexes; Codes; Combinatorics; Convex and Discrete Geometry; Graph theory; Graphs; Mathematical Modeling and Industrial Mathematics; Mathematics; Mathematics and Statistics; Operations Research/Decision Theory; Optimization; Theory of Computation; Vertex sets
• ISSN: 1382-6905; 1573-2886
• DOI: 10.1007/s10878-023-01090-x

Let G be a graph with vertex set V and a subset D ⊆ V . D is a total dominating set of G if every vertex in V is adjacent to a vertex in D . D is a restrained dominating set of G if every vertex in V \ D is adjacent to a vertex in D and another vertex in V \ D . D is a total restrained dominating set if D is both a total dominating set and a restrained dominating set. The minimum cardinality of total dominating sets (resp. restrained dominating sets, total restrained dominating sets) of G is called the total domination number (resp. restrained domination number , total restrained domination number ) of G , denoted by γ t ( G ) (resp. γ r ( G ) , γ tr ( G ) ). The MINIMUM TOTAL RESTRAINED DOMINATION (MTRD) problem for a graph G is to find a total restrained dominating set of minimum cardinality of G . The TOTAL RESTRAINED DOMINATION DECISION (TRDD) problem is the decision version of the MTRD problem. In this paper, firstly, we show that the TRDD problem is NP-complete for undirected path graphs, circle graphs, S-CB graphs and C-CB graphs, respectively, and that, for a S-CB graph or C-CB graph with n vertices, the MTRD problem cannot be approximated within a factor of ( 1 - ϵ ) ln n for any ϵ > 0 unless N P ⊆ D T I M E ( n O ( loglog n ) ) . Secondly, for a graph G , we prove that the problem of deciding whether γ r ( G ) = γ tr ( G ) is NP-hard even when G is restricted to planar graphs with maximum degree at most 4, and that the problem of deciding whether γ t ( G ) = γ tr ( G ) is NP-hard even when G is restricted to planar bipartite graphs with maximum degree at most 5. Thirdly, we show that the MTRD problem is APX-complete for bipartite graphs with maximum degree at most 4. Finally, we design a linear-time algorithm for solving the MTRD problem for generalized series–parallel graphs.